Dowód lematu pompowania dla języków bezkontekstowych za pomocą automatów pushdown

Lemat o pompowaniu dla języków regularnych może być udowodnione przez rozważa automat skończony, który rozpoznaje stan języka badanego, zbierając ciąg o długości większej niż jego liczby stanów i stosując zasadę zaszufladkować. Jednak pompowanie lematu dla języków bezkontekstowych (a także lematu Ogdena, który jest nieco bardziej ogólny), zostało udowodnione poprzez rozważenie bezkontekstowej gramatyki badanego języka, wybranie odpowiednio długiego łańcucha i spojrzenie na drzewo analizy.

Biorąc pod uwagę podobieństwo dwóch pompujących lematów, można oczekiwać, że bezkontekstowy można również udowodnić w podobny sposób do zwykłego, biorąc pod uwagę automat pushdown, który rozpoznaje język, a nie gramatykę. Nie udało mi się jednak znaleźć żadnego odniesienia do takiego dowodu.

Stąd moje pytanie: czy istnieje dowód na pompowanie lematu dla języków bezkontekstowych, które obejmuje tylko automaty wypychające, a nie gramatykę?

Znów pomyślałem o tym problemie i wydaje mi się, że mam pełny dowód. Jest to nieco trudniejsze niż się spodziewałem. Komentarze są bardzo mile widziane! Aktualizacja: przesłałem ten dowód na arXiv, na wypadek, gdyby był on przydatny dla kogoś: http://arxiv.org/abs/1207.2819

$\DeclareMathOperator{\fp}{fp}$ $\DeclareMathOperator{\lp}{lp}$ $\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$ $\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$

Niech będzie językiem bezkontekstowym nad alfabetem . Niech będzie automatem przesuwającym rozpoznającym , z alfabetem stosu . Oznaczamy przezliczba stanów . Bez utraty ogólności możemy założyć, że przejścia przesuwają najwyższy symbol stosu i albo nie pchają żadnego symbolu na stosie, albo wciskają na stosie poprzedni najwyższy symbol i jakiś inny symbol.Σ A L Γ | A | A $L$$\Sigma$$A$$L$$\Gamma$$|A|$$A$$A$

Definiujemyi długość pompowania, i pokaże, że wszystkie takie, że mają rozkład postaci taki, że , i .p = | A | ( | Γ | + 1 ) p ′ w ∈ L | w | > p w = u $p' = |A|^2 |\Gamma|$$p = |A| (|\Gamma|+1)^{p'}$$w \in L$$|w| > p$| v x y | ≤ p | v y | ≥ 1 ∀ n ≥ 0 , u v n$w = u v x y z$$|vxy| \leq p$$|vy| \geq 1$$\forall n \geq 0, u v^n x y^n z \in L$

Niech taki, że . Niech będzie ścieżką akceptującą o minimalnej długości dla (reprezentowaną jako sekwencja przejść ), oznaczamy jej długość przez. Możemy zdefiniować dla, rozmiar stosu w pozycji ścieżki akceptującej. Dla wszystkich , możemy zdefiniować -level nad jako zestaw trzech indeksów z takie, że:| w | > p π w A | π | 0 ≤ i < | π | s ja$w \in L$$|w| > p$$\pi$$w$$A$$|\pi|$$0 \leq i < |\pi|$$s_i$$i$N π i , j , k 0 ≤ i < j < k ≤ $N > 0$$N$$\pi$$i, j, k$$0 \leq i < j < k \leq p$

1. $s_i = s_k, s_j = s_i + N$
2. dla wszystkich takich, że ,i ≤ n ≤ j s i ≤ s n ≤ s $n$$i \leq n \leq j$$s_i \leq s_n \leq s_j$
3. dla wszystkich takich, że , .j ≤ n ≤ k s k ≤ s n ≤ s $n$$j \leq n \leq k$$s_k \leq s_n \leq s_k$

(Na przykład, patrz zdjęcie dla przypadku 2 poniżej, które ilustruje poziom ).$N$

Określamy poziomu o jako maksymalna w taki sposób, ma -level. Definicja ta jest motywowana następującą właściwością: jeśli rozmiar stosu na ścieżce się większy niż jego poziom , wówczas symbole stosu o głębokości większej niż poziomów nigdy nie zostaną usunięte. Rozróżnimy teraz dwa przypadki: albo , w którym to przypadku wiemy, że ta sama konfiguracja dla stanu automatu i najwyższe symboli stosu występują dwa razy w pierwszych krokach , lubπ N π N π l l l < p ′ l p + 1 π l ≥ p ′ v $l$$\pi$$N$$\pi$$N$$\pi$$l$$l$$l < p'$$l$$p+1$$\pi$$l \geq p'$, i musi istnieć pozycja stosu i rozpakowywania, którą można powtórzyć dowolną liczbę razy, z których budujemy i .$v$$y$

Przypadek 1. . Możemy zdefiniować konfiguracje jak par stanie i sekwencji symboli stos (gdzie stosy wielkości mniejszej niż ze reprezentowany przez dopełnienie ich do ze specjalnym symbolem pustym, dlatego używamy przy definiowaniu ). Z definicji są takich konfiguracji, czyli mniej niż . Dlatego w pierwszych krokach ta sama konfiguracja występuje dwa razy w dwóch różnych pozycjach, powiedzmy . Oznacz przez A A l l l | Γ | + 1 p | A | ( | Tt | + 1 ), l s s + 1 π I < J i J W I j π i ≤ J W = U v x y oo r oo = ε U = $l < p'$$A$$A$$l$$l$$l$$|\Gamma| + 1$$p$$|A| (|\Gamma| + 1)^l$$p$$p+1$$\pi$$i < j$$\widehat{i}$ (odpowiednio. ) pozycja ostatniej litery przeczytanej w kroku (odpowiednio. ) z . Mamy . Dlatego możemy uwzględnić z , , , . (W w oznaczamy litery od włącznie do wyłączne.) Według budowy, .$\widehat{j}$$w$$i$$j$$\pi$$\widehat{i} \leq \widehat{j}$$w = u v x y z$$y z = \epsilon$ v= w I ⋯ j x= w j ⋯ | w | w x ⋯ y wxy | vxy | ≤$u = w_{0 \cdots \widehat{i}}$$v = w_{\widehat{i} \cdots \widehat{j}}$$x = w_{\widehat{j} \cdots |w|}$$w_{x \cdots y}$$w$$x$$y$$|vxy| \leq p$

Musimy również wykazać, że , ale wynika to z naszej powyższej obserwacji: symbole stosu głębsze niż nigdy nie są wyskakiwane, więc nie ma możliwości rozróżnienia konfiguracje, które są równe zgodnie z naszą definicją, a ścieżka akceptowania dla jest budowana na podstawie , powtarzając kroki od do , razy.L U v n X w ı j $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$$l$$u v^n x$$w$$i$$j$$n$

Wreszcie mamy też , ponieważ jeśli , to dlatego, że mamy taką samą konfigurację w krokach i w , byłoby ścieżką akceptującą dla , sprzeczną z minimalnością .v = ϵ i j π π ′ = π 0 ⋯ i π j ⋯ | π | w $|v| > 0$$v = \epsilon$$i$$j$$\pi$$\pi' = \pi_{0 \cdots i} \pi_{j \cdots |\pi|}$$w$$\pi$

(Zauważ, że ten przypadek polega na zastosowaniu lematu pompującego dla zwykłych języków poprzez zakodowanie na stałe najwyższych symboli stosu w stanie automatu, co jest wystarczające, ponieważ jest wystarczająco małe, aby zapewnić, że jest większy niż liczba stanów tego automatu Główną sztuczką jest to, że musimy dostosować się do -transitions).l | w | $l$$l$$|w|$$\epsilon$

Przypadek 2. . Niech będą poziomem . Do dowolnego rozmiaru stosu , , kojarzymy ostatnie push i pierwszy pop . Z definicji oraz . Oto ilustracja tej konstrukcji. Aby uprościć rysunek, pomijam rozróżnienie między pozycjami ścieżki i pozycjami słów, które będziemy musieli zrobić później. i , j , k p ′ h s i ≤ h ≤ s j lp ( h ) = max ( { y ≤ j | s y = h } ) fp ( h ) = min ( { y ≥ j | s y = h } ) i ≤ lp ( $l \geq p'$$i, j, k$$p'$$h$$s_i \leq h \leq s_j$ $\lp(h) = \max(\{y \leq j | s_y = h\})$ $\fp(h) = \min(\{y \geq j | s_y = h\})$j ≤ fp ( h ) ≤ $i \leq \lp(h) \leq j$$j \leq \fp(h) \leq k$

Mówimy, że pełny stan stosu o wielkości jest potrójny utworzony przez:$h$

1. stan automatu w pozycji$\lp(h)$
2. symbol najwyższego stosu w pozycji$\lp(h)$
3. stan automatu w pozycji$\fp(h)$

Istnieją możliwe pełne stany, a rozmiary stosu między i , więc zgodnie z zasadą pidgeonhole istnieją dwa rozmiary stosu z takie, że pełne stany w i są takie same. Podobnie jak w przypadku 1, definiujemy za pomocą , , i pozycje ostatnich liter odczytanych na odpowiednich pozycjach w . Współczynnik gdziep ′ + 1 s i s j g , h s i ≤ g < h ≤ s j g h ^ lp ( g ) ^ lp ( h ) ^ fp ( h ) ^ fp ( g ) w π g ) v = w ^ lp ( g ) ⋯ ^ lp ($p'$$p' + 1$$s_i$$s_j$$g, h$$s_i \leq g < h \leq s_j$$g$$h$$\lpp(g)$$\lpp(h)$$\fpp(h)$$\fpp(g)$$w$$\pi$u = w 0 ⋯ ^ lp $w = u v x y z$$u = w_{0 \cdots \lpp(g)}$, , , oraz .$v = w_{\lpp(g) \cdots \lpp(h)}$ y = w ^ fp ( h ) ⋯ ^ fp ( g ) z = w ^ fp ( g ) ⋯ | w $x = w_{\lpp(h) \cdots \fpp(h)}$$y = w_{\fpp(h) \cdots \fpp(g)}$$z = w_{\fpp(g) \cdots |w|}$

Faktoryzacja zapewnia, że (ponieważ według naszej definicji poziomów).k ≤ $|vxy| \leq p$$k \leq p$

Również wykazać, że . Aby to zrobić, zauważ, że za każdym razem, gdy powtarzamy , zaczynamy od tego samego stanu i tego samego stosu i nie spadamy poniżej naszej aktualnej pozycji na stosie (w przeciwnym razie musielibyśmy pchać ponownie w bieżącej pozycji, naruszając maksimum ), więc możemy podążać tą samą ścieżką w i wcisnąć tę samą sekwencję symboli na stos. Dzięki maksymalnemu i minimalnemu , podczas odczytu , nie spadamy poniżej naszej aktualnej pozycji na stosie, więc ścieżka podążająca w automacie jest taka sama bez względu na liczbę razy powtarzaliśmyv lp ( g ) A lp ( h ) fp ( h ) x v w v v v fp ( g ) A u v n x y n z $\forall n \geq 0, u v^n x y^n z \in L$$v$$\lp(g)$$A$$\lp(h)$$\fp(h)$$x$$v$. Teraz, jeśli powtarzamy tyle razy, ile powtarzamy , ponieważ zaczynamy od tego samego stanu, ponieważ wypchnęliśmy tę samą sekwencję symboli na stosie z naszymi powtórzeniami , i ponieważ nie wyskakujemy więcej niż to, co ma ułożone w stos za pomocą minimalnej liczby , możemy podążać tą samą ścieżką w i wyrzucić tę samą sekwencję symboli ze stosu. Stąd, ścieżka akceptowania z może być zbudowana ze ścieżki akceptacji dla .$w$$v$$v$$v$$\fp(g)$$A$$u v^n x y^n z$$w$

Wreszcie mamy też , ponieważ podobnie jak w przypadku 1, jeśli i , możemy zbudować krótszą ścieżkę akceptującą dla , usuwając i .v = ϵ y = ϵ w π lp ( g ) ⋯ lp ( h ) π fp ( h ) ⋯ fp ( g $|vy| > 1$$v = \epsilon$$y = \epsilon$$w$$\pi_{\lp(g)\cdots\lp(h)}$$\pi_{\fp(h)\cdots\fp(g)}$

Dlatego w obu przypadkach mamy odpowiednią faktoryzację, a wynik został udowodniony.

(Podziękowania należą się Marcowi Jeanmouginowi za pomoc w uzyskaniu tego dowodu).

Tak to mozliwe. Przydałoby się pojęcie konfiguracji powierzchni; zostały wprowadzone przez Cooka dawno temu. Dzięki temu powinno być dość łatwo uzyskać wersję pompowania lematu.

Jeśli chodzi o konfiguracje powierzchni, prawie każdy papier w LogCFL powinien mieć swoją definicję. Oto ostatnia praca i tutaj jest teza

Może ktoś bardziej energiczny może przeliterować szczegóły!

Dla kompletności odniesienie do dowodu w tym kierunku.

A.Ehrenfeucht, HJHoogeboom, G.Rozenberg: Skoordynowane systemy par. I: Dyck słowa i klasyczne pompowanie RAIRO, Inf. Théor. Appl. 20, 405–424 (1986)

Abstrakcyjny. Pojęcie skoordynowanego układu par [...] bardzo ściśle odpowiada (jest innym sformułowaniem) pojęciu automatu odpychającego. W tym artykule [...] badamy możliwość uzyskania właściwości pompowania języków bezkontekstowych poprzez analizę obliczeń w systemach CP. W tym celu analizujemy kombinatoryczną strukturę słów Dyck. Właściwości badanych słów Dycka wynikają z kombinatorycznej analizy obliczeń w układach cp. Pokazujemy, jak tę korespondencję można wykorzystać do udowodnienia klasycznego lematu pompowania.

Omawiając ten problem z Géraudem Sénizerguesem, wskazał mi ten artykuł Sakarovitcha, który już potwierdza ten wynik. Wydaje się, że dowód pochodzi z tego artykułu Ogdena.

Referencje:

• Sakarovitch, Jacques. Sur une propriété d'itération des langages algébriques déterministes. (Francuski. Streszczenie w języku angielskim). Matematyka Systems Theory 14 (1981), no. 3, 247–288.
• William F. Ogden. 1969. Twierdzenia o interkalacji dla języków stosu. W materiałach z pierwszego dorocznego sympozjum ACM na temat teorii obliczeń (STOC '69).