Pierwszą sztuczką jest myślenie o tablicy mnożenia jako tabeli przejścia automatu gdzie każdy stan reprezentuje literę w tablicy mnożenia, ale nie martwi się jeszcze o akceptację. Tak więc litery po lewej stronie i w treści tabeli są w rzeczywistości stanami - dokładniej byłoby zapisać je jako , ale nie zrobię tego. Litery u góry to dane wejściowe.Aqa,qb,qc
Następnie skonstruuj automat („ ” do transpozycji) do odwrotnego mnożenia przez transponowanie :ATTA
ATabcaaacbcabcbca
Więc powoduje przejście do stanu , a także przemieszcza się do stanu od , jak można zauważyć.A(abc)cAT(cba)aAT
Jednak zakłada, że idziesz od prawej do lewej, a my nadal chcemy iść od lewej do prawej. Druga sztuczka polega na odwróceniu automatu (a nie na pomnożeniu, które by nas tylko odzyskało, gdybyśmy zaczęli), poprzez odwrócenie wszystkich strzałek, co prowadzi do niedeterministycznego automatu podanego w tabeli przejścia poniżej, z podzbiorami oznaczonymi połączonymi literami, aby kurczak się nie drapał, więc to naprawdę . (mam nadzieję, że wszystko w porządku - wydaje się działać).ATATRac{ a , c }
ZAT.Rzabdoa bb cCa b c∅zaa b∅doa bdoa b ca b c∅bbdozab cCa ba b c∅dodozabCa b cb ca b c∅
Możesz zinterpretować to jako niedeterministyczny automat z tylko trzema rzędami powyżej linii lub zdeterminowaną wersję ze wszystkimi 8 rzędami.
Wreszcie, maszyną do rozwiązania problemu jest automat międzyplatformowy oryginalnych i , czyli do wykonania zachowania przecięcia dwóch automatów (nie potrzebujemy żadnych więcej). ma stany, które są parami takimi jak . Funkcja przejścia uruchamia i niezależnie. Pojedynczy stan początkowy przechodzi do pod wejściem , do pod wejściem itp. ZAZAT.RA ×ZAT.RZAT.A ×ZAT.R⟨ , C ⟩ZAZAT.R⟨ 1 , 1 ⟩⟨ , ⟩za⟨ B , b ⟩b
Stany akceptujące w wersji niedeterministycznej to itp. W wersji deterministycznej stany akceptujące to pary, w których pierwszy komponent znajduje się drugim zestawie komponentów, takich jak lub .⟨ , ⟩∈⟨ , ⟩⟨ B , b c ⟩
A ×ZAT.R rozszerzony i zdeterminowany, jak pokazano, ma stanów, więc wybacz mi, jeśli nie wypiszę go szczegółowo. Ale wersja niedeterministyczna ma tylko stanów.25 = 3 ⋅ 8 + 110 = 3 ⋅ 3 + 1
W jaki sposób pomaga nam to rozwiązać problem? PozwolićL.za,L.b,L.do być językami składającymi się ze wszystkich ciągów, które oceniają na a , b , c przy ocenie od lewej do prawej. Językiem, którym jesteś zainteresowany
W rzeczywistości, jeśli skorzystasz z idei dowodu(∗) , to prawdopodobnie możesz po prostu zbudować automat. Rozważmy to. W szczególności spróbujmy zbudować NFA dlaLRa , język wszystkich ciągów, które oceniają na a oceniany od prawej do lewej.
Chodzi o to, że. Załóżmy, że pierwsza litera, którą widzisz, tob . Następnie reszta ciągu musi oceniać nab (od bx=a implikuje x=b ). Podobne rozumowanie stosuje się, gdy pierwszą literą jestc . Kiedy pierwsza litera toa , jednak reszta może ocenić albo a lub b lub być zerowy. Dzięki NFA możemy zgadywać (a później weryfikować nasze przypuszczenia).
Ta wskazówka powinna dać ci wystarczająco dużo do myślenia i, mam nadzieję, rozwiązać problem.
źródło
Uroczy.
Najpierw zbuduj automat, który oblicza produkt od lewej do prawej. Łatwy! Umieść przejściex→−→yz→ kiedy tylko x⋅y=z . Istnieją trzy stany{a→,b→,c→} reprezentujący trzy możliwe produkty. Zacznij od czwartego stanu1→ z 1→−→−xx→ dla wszystkich x . Ostateczny stan tox→ tylko wtedy, gdy iloczynem słowa wejściowego od lewej do prawej jest x .
Zbudujmy teraz automat, który oblicza produkt od prawej do lewej. Ten będzie niedeterministyczny. Jak to zrobimy? Proste… Aby przejść w innym kierunku, po prostu odwróć wszystko : strzałki i kierunek produktu.
Dodaj rozłączony węzeł1← ze względu na puste słowo. Wszystkie węzły są początkowe.
Teraz musimy obliczyć obie ścieżki razem, więc bierzemy iloczyn dwóch automatów:(x1→,x2←)−→y(z1→,z2←) iff x1→−→yz1→ i x2←−→yz2← . Niech cztery stany(1→,x←) być początkowym, a cztery stany (x→,x←) być ostatecznym. Słowo jest rozpoznawane przez ten niedeterministyczny automat w produkcie od lewej do prawej, a jego produkt od prawej do lewej jest taki samx .
źródło
Wygląda na to, że twoim głównym problemem jest niedeterminizm, więc pozwól mi rozwinąć tę kwestię.
Rozważmy twój mały przykłada b c i pomysł konstrukcyjny Gillesa. Automat „obliczający” produkt od prawej do lewej na początku zgaduje wynik i weryfikuje go. Istnieją więc trzy możliwości:
Jak widać, NFA jest w stanie odgadnąć i sprawdzić wszystkie możliwe obliczenia oddolne . Ponieważ zaakceptowany język jest zdefiniowany jako zestaw ciągów, który jest akceptowany przez co najmniej jedno uruchomienie , wszystkie niedopuszczalne przebiegi na danych wejściowych są ignorowane; NFA „zawsze zgaduje”.
Teraz NFA łatwo zapamiętuje swój pierwszy wybór do końca. Jeśli się zgadza, może porównać zapamiętany symbol z produktem lr (deterministycznie) uzyskanym równolegle (sposób, w jaki przecięcie języka odnosi się do NFA, jest z pewnością omówione w Ullman / Hopcroft i każdym innym podstawowym podręczniku).
źródło