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

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ą:

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

Więc jeśli mamy ciąg , iloczyn od lewej do prawej to a iloczyn od prawej do lewej to$abc$
$(a \times b) \times c=a \times c=c$
$a \times (b \times c)=a \times 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ęć).$abc$$aa^*$$bb^*$$cc^*$

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

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.$A$$q_a, q_b, q_c$

Następnie skonstruuj automat („ ” do transpozycji) do odwrotnego mnożenia przez transponowanie :$A_T$$T$$A$

$\qquad \displaystyle\begin{array}{c|ccc} A_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

Więc powoduje przejście do stanu , a także przemieszcza się do stanu od , jak można zauważyć.$A(abc)$$c$$A_T(cba)$$a$$A_T$

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ć).$A_T$$A_{TR}$$ac$$\{a,c\}$

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

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. $A$$A_{TR}$$A \times A_{TR}$$A_T$$A \times A_{TR}$$\langle a,ac\rangle$$A$$A_{TR}$$\langle 1,1 \rangle$$\langle a,a \rangle$$a$$\langle b,b \rangle$$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 .$\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

$A \times A_{TR}$ 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\cdot 8+1$$10=3\cdot 3+1$

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

W jaki sposób pomaga nam to rozwiązać problem? Pozwolić$L_a,L_b,L_c$ 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$(\ast)$, to prawdopodobnie możesz po prostu zbudować automat. Rozważmy to. W szczególności spróbujmy zbudować NFA dla$L_a^R$, 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, to$b$. Następnie reszta ciągu musi oceniać na$b$ (od $bx = a$ implikuje $x = b$). Podobne rozumowanie stosuje się, gdy pierwszą literą jest$c$. Kiedy pierwsza litera to$a$, 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.

Uroczy.

Najpierw zbuduj automat, który oblicza produkt od lewej do prawej. Łatwy! Umieść przejście$\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$ kiedy tylko $x \cdot y = z$. Istnieją trzy stany$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$reprezentujący trzy możliwe produkty. Zacznij od czwartego stanu$\overrightarrow 1$ z $\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$ dla wszystkich $x$. Ostateczny stan to$\overrightarrow x$ 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 $\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$, teraz bierzemy $\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$: kiedy używamy słowa od lewej do prawej, przechodzimy od produktu do jego czynnika po prawej stronie. Lub innymi słowy$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$.

Dodaj rozłączony węzeł $\overleftarrow 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: $(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$ iff $\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$ i $\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$. Niech cztery stany$(\overrightarrow 1, \overleftarrow x)$ być początkowym, a cztery stany $(\overrightarrow x, \overleftarrow 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 sam$x$.

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 $abc$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:

• Odgadnąć $a$: Jak pierwszy symol $a$, produkt rl z $bc$ musiało $a$ lub $b$.
  • Odgadnąć $a$: Jak drugi symbol $b$, ostatnim symbolem musiał być $b$.
    • (Odgadnąć $b$:) To jest $c$, 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 $c$, 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).