Łatwy dowód na zamknięcie języków bezkontekstowych podczas cyklicznej zmiany

Przesunięcia cyklicznego (zwany również obracanie lub koniugacji ) języka jest zdefiniowana jako . Według wikipedii (i tutaj ) języki bezkontekstowe są zamknięte w ramach tej operacji, z odniesieniami do artykułów z Osziby i Masłowa. Czy istnieje łatwy dowód tego faktu?$L$$\{ yx \mid xy \in L \}$

W przypadku zwykłych języków zamknięcie omawia się w tej formie jako „ Wykazać, że zwykłe języki są zamknięte pod operatorem cyklu ”.

Możesz spróbować użyć automatów pushdown. Biorąc pod uwagę automatyczny system przesunięcia dla oryginalnego języka, konstruujemy jeden dla cyklicznego przesunięcia. Nowy automat działa w dwóch etapach, odpowiadających części i słowa (gdzie jest w oryginalnym języku). W pierwszym etapie, ilekroć automat chciałby otworzyć nie-terminal , może zamiast tego naciskać na nie-terminal ; Chodzi o to, że na końcu pierwszego etapu stos będzie zawierał w odwrotnej kolejności symbole, które zostaną znalezione na stosie po odczytaniu przez oryginalny automat. W drugim etapie (przełącznik nie jest deterministyczny), zamiast naciskać nieterminalny$y$$x$$yx$$xy$$A$$A'$$x$$A$, wolno nam wyskoczyć z terminala . Jeśli oryginalny automat rzeczywiście może wygenerować stos po odczytaniu , nowy byłby w stanie dokładnie zniszczyć cały stos.$A'$$x$

Edycja: Oto kilka dodatkowych szczegółów. Załóżmy, że otrzymaliśmy PDA z alfabetem , zestawem stanów , zestawem stanów akceptujących , nieterminowymi , stanem początkowym i zestawem dopuszczalnych przejść. Każde dopuszczalne przejście ma postać , co oznacza, że ​​w stanie , po odczytaniu (lub , w którym to przypadku jest to przejście swobodne), jeśli na szczycie stosu znajduje się (lub , co oznacza, że ​​stos jest pusty), wówczas PDA może (to model niedeterministyczny) przejść do stanu , zastępującΣ Q F Γ q 0 ( q , a , A , q ′ , α ) q a ∈ A a = ϵ A ∈ Γ A = ϵ q ′ A α ∈ Γ $\Sigma$$Q$$F$$\Gamma$$q_0$$(q,a,A,q',\alpha)$$q$$a \in A$$a = \epsilon$$A \in \Gamma$$A = \epsilon$$q'$$A$ z .$\alpha \in \Gamma^*$

Nowy PDA ma nowy nieterminalny dla każdego . Dla każdego z dwóch stanów i istnieją dwa stany . Stany początkowe (rzeczywisty stan początkowy jest wybierany spośród nich niedeterministycznie za pomocą -transitions) to . Dla każdego przejścia istnieją odpowiednie przejścia i . Istnieją również inne przejścia.A ′ A ∈ Γ q , q ′ ∈ Q A ∈ Γ ∪ { ϵ } ( q , q ′ , 1 ) , ( q , q ′ , 2 , A ) ϵ ( q , q , 1 ) ( q , a , A , q ′ , α ) ( ( q $A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$$(q,q,1)$$(q,a,A,q',\alpha)$q ″ , 1 ) , a , A , ( q ′ , q ″ , 1 ) , α ) ( ( q , q ″ , 2 , B ) , a , A , ( q ′ , q ″ , 2 , B ) , α $((q,q'',1),a,A,(q',q'',1),\alpha)$$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

Dla każdego przejścia istnieją przejścia , gdzie i . Dla każdego stanu końcowego istnieją przejścia , gdzie .( q , a , A , q ′ , α ) ( ( q , q ″ , 1 ) , a , B ′ , ( q ′ , q ″ , 1 ) , B ′ A ′ α ) B ∈ Γ ∪ { ϵ } ϵ ′ = ϵ q ∈ F ( ( q $(q,a,A,q',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$$\epsilon' = \epsilon$$q \in F$q ″ , 1 ) , ϵ , A , ( q 0 , q ″ , 2 , ϵ ) , A ) A ∈ Γ ∪ { ϵ $((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$$A \in \Gamma \cup \{\epsilon\}$

Dla każdego przejścia istnieją przejścia , gdzie . Dla każdego przejścia istnieją przejścia , gdzie . Dla każdego przejścia istnieją „przejścia uogólnione” ; są one realizowane jako sekwencja dwóch przejść przez nowy stan pośredni. Przejścia\ alpha) z( q , a , ϵ , q ′ , α ) ( ( q , q ″ , 2 , A ) , a , B ′ , ( q ′ , q ″ , 2 , A ) , B ′ α ) A ∈ Γ ∪ { ϵ } ( q , a , ϵ , q $(q,a,\epsilon,q',\alpha)$$((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$$A \in \Gamma \cup \{\epsilon\}$, A ) ( ( q , q ″ , 2 , B ) , a , A ′ , ( q ′ , q ″ , 2 , A ) , ϵ ) B ∈ Γ ∪ { ϵ } ( q , a , A , q ′ , B ) ( ( q , q ″ , $(q,a,\epsilon,q',A)$$((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$$B \in \Gamma \cup \{\epsilon\}$$(q,a,A,q',B)$, C ) , a , B ′ A , ( q , q ″ , 2 , C ) , ϵ ) ( q , a , ϵ , q ′ , α ) | α | ≥ 2 ( q , a , A , q ′ , A ) ( ( q , q ″ , 2 $((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$$(q,a,\epsilon,q',\alpha)$$|\alpha| \geq 2$są traktowane podobnie. Dla każdego przejścia istnieją przejścia , gdzie . Przejścia są obsługiwane podobnie. Wreszcie istnieje jedyny stan końcowy i przejścia .$(q,a,A,q',A)$A ) , a , B , ( q ′ , q ″ , 2 , A ) , B ) B ∈ Γ ′ ∪ { ϵ } ( q , a , A , q ′ , A α ) f ( ( q , q , 2 , A ) , ϵ , ϵ , f , $((q,q'',2,A),a,B,(q',q'',2,A),B)$$B \in \Gamma' \cup \{\epsilon\}$$(q,a,A,q',A\alpha)$$f$$((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$

(Może być kilka przejść, które przegapiłem, a niektóre szczegóły, które pomijam, są nieco niechlujne).

Przypomnijmy, że próbujemy zaakceptować słowo , gdzie jest akceptowane przez oryginalny PDA. Stan oznacza, że ​​jesteśmy na etapie 1, w stanie , a oryginalny PDA jest w stanie po odczytaniu . Stan jest podobny, gdzie odpowiada ostatniemu który został przerwany. W etapie 1, wolno nam wcisnąć zamiast popping . Robimy to dla każdego nieterminala, który jest generowany podczas przetwarzania , ale pojawiał się tylko podczas przetwarzania . Na etapie 2 możemy popy x x y ( q , q ′ , 1 ) q q ′ x ( q , q ′ , 2 , A ) A A ′ A ′ A x y A ′ A A ϵ B $yx$$xy$$(q,q',1)$$q$$q'$$x$$(q,q',2,A)$$A$$A'$$A'$$A$$x$$y$$A'$zamiast pchania . Jeśli to zrobimy, musimy pamiętać, że na szczycie jest naprawdę ; dotyczy to tylko sytuacji, gdy na stosie nie ma „tymczasowych” rzeczy, które w symulowanym PDA są takie same, jak na szczycie stosu lub w formie .$A$$A$$\epsilon$$B'$

Oto prosty przykład. Rozważ automat dla który popycha dla każdego i wyskakuje dla każdego . Nowy automat akceptuje słowa dwóch form: i . Dla słów pierwszej postaci, etap 1 składa się z pchania razy„etap 2 składa się pojawiały razy , spychając razy i popping razy . W przypadku słów drugiej formy najpierw wciskamy razyx n y n A x A y y k x n y n - k x k y n x n - k k A ′ k A ′ n - k A n - k A k A k A n - k A ′ n - k A $x^n y^n$$A$$x$$A$$y$$y^k x^n y^{n-k}$$x^k y^n x^{n-k}$$k$$A'$$k$$A'$$n-k$$A$$n-k$$A$$k$$A$, następnie pop razy , push razy , przejście do etapu 2 i pop razy .$k$$A$$n-k$$A'$$n-k$$A'$

Oto bardziej skomplikowany przykład dla języka zrównoważonych nawiasów różnych typów („()”, „[]”, „<>”) tak, że bezpośredni potomkowie każdego typu nawiasów muszą należeć do innego typu. Na przykład „([] <>)” jest OK, ale „()” jest błędne. Dla każdego "(" my pchamy jeśli top-of-stos nie jest dla każdego ")", mamy pop . Podobnie , są powiązane z „[]” i „<>”. Oto, w jaki sposób akceptujemy słowo „>) ([()] <”. Używamy „>)”, przesuwając i przechodząc do etapu 2. konsumujemy „(”, otwierająci pamiętając górnej krawędzi stosu . Używamy „[()]”, popychając i popping ; podczas pchaniaA A A B C C ′ A ′ A ′ A B A B A $A$ $A$$A$$B$$C$$C'A'$$A'$$A$$BA$$B$ , jesteśmy świadomi, że „prawdziwym” szczytem stosu jest , więc nawiasy kwadratowe są dozwolone (nie dałoby się nam oszukać „>) (() <”); kiedy pchasz , ponieważ górą stosu jest (która nie jest ani formy ), to wiemy, że jest również „prawdziwym” szczytem stosu, więc okrągłe nawiasy są dozwolone (nawet jeśli cień na szczycie stosu to ). Wreszcie konsumujemy „<” i pop .$A$$A$ B ϵ X ′ B A C $B$$\epsilon$$X'$$B$$A$$C'$

Rozważ normalną formę Greibacha . Aby zbudować zmieniony język, wystarczy zmienić produkcje na i dodać nowy nieterminalny który zachowuje się jak kiedyś , w przypadku niektórych produkcja odniesienia .S → α A 1 … A n S → A 1 … A n α S ′ S $S \to \alpha A_1 \dots A_n$$S \to A_1\dots A_n \alpha$$S'$$S$$S$

Dobrym pomysłem okazało się sprawdzenie starej klasyki Hopcroft i Ullman Wstęp do teorii automatów (1979). Zamknięcie w cyklu to ćwiczenie 6.4c i oznaczono jako S **. Podwójne gwiazdki oznaczają, że jest to jeden z najtrudniejszych problemów (w książce). Na szczęście S wskazuje, że jest to jeden z wybranych problemów z rozwiązaniem.

Rozwiązanie jest następujące. Weź CFG w normalnej formie Chomsky'ego. Zastanów się nad dowolnym drzewem pochodnym i po prostu odwróć je do góry nogami. Rozważ ścieżkę w oryginalnym drzewie. Z lewej strony drzewo ma wkłady po prawej , co oznacza, że ​​wyprowadzony ciąg równa się . (W rzeczywistości, ponieważ gramatyka jest CNF, gdy ścieżka jest kontynuowana w lewo, wkład będzie w prawo, a odpowiadające jest puste itp.)S = X 1 , X 2 , … , X n x 1 , x 2 , … , x n y 1 , y 2 , … , y n x 1 x 2 … x n y n … y 2 y 1 x $S=X_1, X_2, \dots , X_n$$x_1, x_2, \dots, x_n$$y_1, y_2, \dots, y_n$$x_1 x_2 \dots x_n y_n \dots y_2 y_1$$x_i$

Drzewo do góry nogami ma ścieżkę z wkładami w lewo i w prawo, więc wynik jest pochodną dla . Jako wymagane.S ' , X n , ... X 2 , X 1 Y n , ... , Y 2 r 1 x n , ... , x 2 x 1 r n ... r 2 r 1 x 1 x 2 ... x $S', \hat X_n, \dots \hat X_2, \hat X_1$$y_n, \dots, y_2 y_1$$x_n, \dots, x_2 x_1$$y_n \dots y_2 y_1 x_1 x_2 \dots x_n$

Pełne szczegóły budowy podano w książce.

Zwróć uwagę, jak to przypomina (zaakceptowane) rozwiązanie Yuval. Nieterminale, które są wypychane zamiast wyskakujące, znajdują się na stosie w odwrotnej kolejności. Całkiem podobny do góry nogami na drzewie.