Słowa, które mają ten sam prawy i lewy skojarzony produkt

9

Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący:

Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej do lewej, mnożąc zgodnie z poniższą tabelą:

×abcaaacbcabcbca

Więc jeśli mamy ciąg , iloczyn od lewej do prawej to a iloczyn od prawej do lewej toabc
(a×b)×c=a×c=c
a×(b×c)=a×b=a

Dlatego nie powinien być akceptowalny dla automatów. Dla mnie jest oczywiste, że dowolny łańcuch lub lub jest łańcuchem dopuszczalnym (ich ocena po prawej i lewej stronie działa na tych samych ciągach częściowych). Łatwo jest podać NFA, który opisuje ocenę od lewej do prawej, ale problem polega na tym, że jeśli maszyna próbuje obliczyć ocenę od prawej do lewej , myślę, że musi znać długość łańcucha (więc potrzebna jest nieskończona pamięć).abcaabbdodo

Jak więc niedeterministyczne automaty mogą oceniać od prawej do lewej w celu porównania z oceną od lewej do prawej?

Pan Ariel
źródło

Odpowiedzi:

6

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.ZAqza,qb,qdo

Następnie skonstruuj automat („ ” do transpozycji) do odwrotnego mnożenia przez transponowanie :ZAT.TZA

ATabcaacbbaacccba

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.Rzabdozazabbdobdozadodozabzabzabbdozadobdodozadozabdozadozabdozabbdozabdozabdozabdozabdo

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.RZA×ZAT.RZAT.ZA×ZAT.Rza,zadoZAZAT.R1,1a,aab,bb

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 .a,aa,ab,bc

A×ATR 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=38+110=33+1

David Lewis
źródło
Dzięki, naprawdę pomogło mi to w zrozumieniu idei niedeterminizmu i „odwrotności” automatów. Miałem problemy ze zrozumieniem tych koncepcji, korzystając z książki Hopcroft, a teraz korzystam z książki Sipsera „Wprowadzenie do teorii obliczeń”, która jest naprawdę dobra.
Pan Ariel,
Rozważ dane wejściowe ba. 1,1 przenosi się do b,b po wejściu b, a następnie do c, pod wejściem za, więc bzanie jest akceptowane, ale powinno być?
cemulate
8

() Gdyby L. jest więc zwykłym językiem L.R, język składający się z odwrotnej strony wszystkich wyrazów wL., jest również regularne. Weź to jako ćwiczenie.

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 za,b,doprzy ocenie od lewej do prawej. Językiem, którym jesteś zainteresowany

(LaLaR)(LbLbR)(LcLcR).
To pokazuje, że jeśli wiesz, jak to udowodnić (), możesz utworzyć NFA dla danego języka.

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 dlaLaR, 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 blub 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.

Yuval Filmus
źródło
Dobry sposób, aby to udowodnić za pomocą formuły - głosuj za tym. Jeśli chodzi o alternatywny pomysł „niedeterministycznego odgadywania i weryfikowania”, jest to zwykle OK dla dowodu, ale jest dość trudne do zrealizowania, jak wymaga tego problem. Myślę, że brakuje tutaj wielu szczegółów, takich jak śledzenie łańcucha od tyłu.
David Lewis,
@ David, celowo brakuje szczegółów.
Yuval Filmus
@Yuval - nie powiedział, że to praca domowa - ufamy ludziom, prawda? Myślę również, że ten dowód istnienia zaowocuje całkiem dużą maszyną, prawdopodobnie znacznie większą niż to konieczne.
David Lewis,
@DavidLewis: Gilles udzielił bardziej kompletnej odpowiedzi, która pokazuje, że NFA rzeczywiście nie jest zbyt duży; niedeterminizm robi to za ciebie. Odpowiedni DFA może być jednak ogromny.
Raphael
@MohamedAbbas Być może nie planuję sprawdzać.
Yuval Filmus
6

Uroczy.

Najpierw zbuduj automat, który oblicza produkt od lewej do prawej. Łatwy! Umieść przejściexyz kiedy tylko xy=z. Istnieją trzy stany{a,b,c}reprezentujący trzy możliwe produkty. Zacznij od czwartego stanu1 z 1xx 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.

Gdzie mieliśmy wcześniej xyxy, teraz bierzemy xyxy: kiedy używamy słowa od lewej do prawej, przechodzimy od produktu do jego czynnika po prawej stronie. Lub innymi słowyxyyx.

Dodaj rozłączony węzeł 1ze 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 x1yz1 i x2yz2. 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.

Gilles „SO- przestań być zły”
źródło
Mam trochę kłopotów z tym. Nie musisz tego sprawdzaćxyyxprowadzi do skończonego stanu? IAC, nie jest to tak proste, jak „odwrócenie wszystkiego”, ponieważ nadal musisz konsumować od lewej do prawej, ale pomnażaj od prawej do lewej i nie jestem pewien, czy to zrobiłeś.
David Lewis,
@DavidLewis Zestaw stanów jest skończony, zdefiniowałem go {overleftarrowa,b,b,1}. Odwróciłem kolejność mnożenia (wykluczając więcej literówek).
Gilles 'SO - przestań być zły'
5

Wygląda na to, że twoim głównym problemem jest niedeterminizm, więc pozwól mi rozwinąć tę kwestię.

Podstawową ideą, którą wykorzystują inni, jest to, że niedeterministyczna maszyna może odgadnąć ostateczny wynik.

Rozważmy twój mały przykład zabdoi 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:

  • Odgadnąć za: Jak pierwszy symol za, produkt rl z bdo musiało za lub b.
    • Odgadnąć a: Jak drugi symbol b, ostatnim symbolem musiał być b.
      • (Odgadnąć b:) To jest do, więc nie akceptuj.
    • Odgadnąć b: Jak drugi symbol b, ostatnim symbolem musiał być c.
      • (Odgadnąć c:) W rzeczy samej c, więc akceptujemy.
  • Odgadnąć b: Jak pierwszy symol a, nie jest to możliwe, więc nie akceptuj.
  • Odgadnąć c: Jak pierwszy symol a, produkt rl z bc musiało c
    • (Odgadnąć c:) Tak jak drugi symbol b, ostatnim symbolem musiał być a
      • (Odgadnąć a:) To jest do, więc nie akceptuj.

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).

Raphael
źródło
Pomysł odgadnięcia łańcucha był dla mnie dziwny, ale czytam książkę Sipsera i myślę, że jest to lepsze podejście dla początkujących jak ja w teorii obliczeń.
Pan Ariel,
Pomyśl o zgadywaniu jako rozwidlaniu przy założonym wkładzie. Trzeba jednak uważać na strategie zgadywania - upewnij się, że pamięć potrzebna do zgadywania jest ograniczona równomiernie dla wszystkich rozwidlonych wątków, w przeciwnym razie nie będziesz mieć automatu o skończonej liczbie stanów. Potrzebujemy również jednolitego ograniczenia liczby aktywnych wątków rozwidlonych. Myślę, że opis Raphaela tutaj działa, ale należy o nim przynajmniej wspomnieć.
David Lewis,