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

11

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 L{ y x x y L }{yxxyL}

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

Hendrik Jan
źródło

Odpowiedzi:

5

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ć nieterminalnyy yx xy x yxx y xyA AA A x xAA, 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 A xx

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 α Γ ΣQFΓq0(q,a,A,q,α)qaAa=ϵAΓA=ϵqA z .αΓ

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 ,AAΓq,qQAΓ{ϵ}(q,q,1),(q,q,2,A)ϵ(q,q,1)(q,a,A,q,α)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),α)((q,q′′,2,B),a,A,(q,q′′,2,B),α)

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, α )( ( q, q′ ′, 1 ) , a , B, ( q, q′ ′, 1 ) , BZAα )B Γ { ϵ }ϵ= ϵqF.q , 1 ) , ϵ , A , ( q 0 , q , 2 , ϵ ) , A ) A Γ { ϵ }( ( q, q′ ′, 1 ) , ϵ , A , ( q0, q′ ′, 2 , ϵ ) , A )A Γ { ϵ }

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,ϵ,q,α)((q,q′′,2,A),a,B,(q,q′′,2,A),Bα)AΓ{ϵ}, A ) ( ( q , q , 2 , B ) , a , A , ( q , q , 2 , A ) , ϵ ) B Γ { ϵ } ( q , a , A , q , B ) ( ( q , q , 2(q,a,ϵ,q,A)((q,q′′,2,B),a,A,(q,q′′,2,A),ϵ)BΓ{ϵ}(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,BA,(q,q′′,2,C),ϵ)(q,a,ϵ,q,α)|α|2są 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Γ{ϵ}(q,a,A,q,Aα)f)((q,q,2,A),ϵ,ϵ,f,ϵ)

(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 yxxy(q,q,1)qqx(q,q,2,A)AAAAxyAzamiast 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 .AAϵ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 xnynAxAyykxnynkxkynxnkkAkAnkAnkAkA, następnie pop razy , push razy , przejście do etapu 2 i pop razy .kAnkAnkA

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 AA AABCCAAABAB , 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 .AA B ϵ X B A C BϵXBAC

Yuval Filmus
źródło
Przepraszam, mam problem ze zrozumieniem - czy możesz wyjaśnić dalej? Gdzie zaczyna się automat i jakie są jego przejścia? I czy przełącznik występuje dla każdego symbolu stosu? Dzięki! A A AA
usul
Bardzo interesująca sugestia. Dzięki. Przygryzę to trochę, żeby się zagłębiło.
Hendrik
@usul, musisz samodzielnie wypełnić dane. Przełącznik prawy (w pierwszym etapie) powinien nastąpić, gdy automat „chce” nacisnąć ale nie może, a zamiast tego naciska . Można to uznać za ruch niedeterministyczny. A A A A AA
Yuval Filmus
@Yuval: przepraszam, ale nie mogę tego zrobić. Jak rozumiem twój pomysł, nowy automat zaczyna się od symulacji części , zmiany trzasków i przesunięć. Następnie wygeneruj na stosie, gdzie oryginalny automat zaczyna się od podczas czytania . Waht to oryginał zaczyna się od pchania? Następnie automat nwe musi wyskoczyć z pustego stosu. Nadal uważam, że Twoja intuicja jest warta zachodu, ale wydaje się, że potrzebna jest dodatkowa ostrożność. y α α y
Hendrik Jan
@Hendrik, przepraszam, ale nie mogę śledzić twojego kontrprzykładu. Jak myślisz, w którym momencie nowy automat musi wyskoczyć z pustego stosu?
Yuval Filmus
4

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 1A n S A 1A n α S S S

Karolis Juodelė
źródło
Dzięki, ale to przesunięcie o jedną literę. Interesuje mnie ogólna rotacja według dowolnej liczby liter.
Hendrik Jan
3
@HendrikJan, cóż, jeśli zawiera kontekstu, więc z pewnością również nie będą miały kontekstu. Możesz zbudować dla niego gramatykę, stosując metodę, którą zasugerowałem razy. Możesz także zbudować gramatykę bezpośrednio, „spłaszczając” gramatykę Na przykład, jeśli a gramatyka ma produkcje i , należy dodać produkcyjną i obrócić ją. Oczywiście rozmiar Twoja gramatyka może urosnąć bardzo szybkoprzesunięcie 1 ( L ) przesunięcie n ( L ) = przesunięcie 1 ( przesunięcie 1 ( ( L ) ) n przesunięcie n ( L ) n = 2 S α A B A β C S α β C B
Karolis Juodelė
1
Dla ustalonego masz rację. Ale tutaj jest ustalone lub ograniczone. Na przykład, jeśli wówczas otrzymamy . n n L = { a n b nn 0 } { a k b n a k + = n } { b k a n b k + = n }
Hendrik Jan
@HendrikJan, rozumiem. Błędnie założyłem, że pytanie dotyczy zmiany skończonej.
Ponownie rozważę
4

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 2x n y ny 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 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.

Hendrik Jan
źródło