Jak udowodnić, że język nie jest pozbawiony kontekstu?

Dowiedzieliśmy się o klasie języków bezkontekstowych . Charakteryzuje się zarówno gramatykami bezkontekstowymi, jak i automatami pushdown, dzięki czemu łatwo jest pokazać, że dany język jest pozbawiony kontekstu.$\mathrm{CFL}$

Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich gramatyk (lub automatów), że nie potrafią opisać języka, który jest pod ręką. To wydaje się dużym zadaniem!

Czytałem o lemie pompującym, ale wygląda to na bardzo skomplikowane.

Według mojej wiedzy lemat pompujący jest zdecydowanie najprostszą i najczęściej stosowaną techniką. Jeśli jest ci ciężko, wypróbuj najpierw zwykłą wersję , nie jest tak źle. Istnieją inne sposoby dla języków, które są dalekie od kontekstu. Na przykład niezdecydowane języki nie są trywialnie wolne od kontekstu.

To powiedziawszy, interesują mnie również inne techniki niż lemat pompowania, jeśli takie istnieją.

EDYCJA: Oto przykład lematu pompującego: załóżmy, że język jest pozbawiony kontekstu ( jest zbiorem liczb pierwszych). Lemat pompujący ma wiele kwantyfikatorów więc sprawię, że będzie to trochę jak gra:P ∃ / $L=\{ a^k \mid k ∈ P\}$$P$$∃/∀$

1. Lemat pompowania daje$p$
2. Dajesz słowo języka o długości co najmniej$s$$p$
3. Lemat pompujący przepisuje to w następujący sposób: z pewnymi warunkami ( i )| v x y | ≤ p | v y | ≥ $s=uvxyz$$|vxy|≤p$$|vy|≥1$
4. liczbę całkowitą$n≥0$
5. Jeśli nie jest w , wygrywasz, nie jest pozbawiony kontekstu.L $uv^nxy^nz$$L$$L$

W tym konkretnym języku dla dowolny (z oraz jest liczbą pierwszą) rade. Wtedy lemat pompujący daje ci z . Nie obalaj kontekstowości, musisz znaleźć takie, żenie jest liczbą pierwszą.a k k ≥ p k u v x y z | v y | ≥ 1 n | u v n x y n z $s$$a^k$$k≥p$$k$$uvxyz$$|vy|≥1$$n$$|uv^nxy^nz|$

A następnie zrobi: nie jest liczbą pierwszą, tak . Nie można zastosować lematu pompującego, więc nie jest pozbawiony kontekstu.k + k | v y | = k ( 1 + | v y | ) u v n x y n z ∉ L $n=k+1$$k+k|vy|=k(1+|vy|)$$uv^nxy^nz\not\in L$$L$

Drugim przykładem jest język . Musimy (oczywiście) wybrać ciąg znaków i pokazać, że nie ma możliwości podzielenia go na te pięć części i że każdy wyprowadzony ciąg znaków pozostaje w języku.$\{ww \mid w \in \{a,b\}^{\ast}\}$

Ciąg jest odpowiednim wyborem dla tego dowodu. Teraz musimy tylko sprawdzić, gdzie mogą znajdować się i . Najważniejsze jest to, że lub musi mieć coś w sobie (być może jedno i drugie) i że zarówno i (i ) są zawarte w podciągu długości - więc nie mogą być zbyt daleko od siebie. v y v y v y x $s=a^{p}b^{p}a^{p}b^{p}$$v$$y$$v$$y$$v$$y$$x$$p$

Ten ciąg ma wiele możliwości, gdzie mogą znajdować się i , ale okazuje się, że kilka przypadków faktycznie wygląda całkiem podobnie.$v$$y$

1. v y ∈ b ∗ a b | v y | = k ≤ $vy \in a^{\ast}$ lub . Tak więc oba są zawarte w jednej z sekcji zakreślających s lub s. Jest to stosunkowo łatwy argument, ponieważ nie ma znaczenia, w którym są. Załóżmy, że . $vy \in b^{\ast}$$a$$b$$|vy| = k \leq p$
   • Jeśli są w pierwszym odcinku s, a następnie kiedy pompa, pierwsza połowa nowego łańcucha jest , a drugi jest . Oczywiście nie ma to formy .a p + k b p - k / 2 b k / 2 a p b p w $a$$a^{p+k}b^{p-k/2}$$b^{k/2}a^{p}b^{p}$$ww$
   • Argument dla każdej z trzech innych sekcji działa prawie tak samo, tylko tam, gdzie i kończą się na indeksach.k /$k$$k/2$
2. $vxy$ rozciąga się na dwie sekcje. W tym przypadku pompowania w dół jest twoim przyjacielem. Znów jest kilka miejsc, w których może się to zdarzyć (dokładnie 3), ale zrobię tylko jedno ilustracyjne, a reszta powinna być łatwa do zrozumienia.
   • Załóżmy, że leży na granicy pomiędzy pierwszym sekcji i pierwszym sekcji. Niech (nie ma znaczenia dokładnie, gdzie si są w i , ale wiemy, że są w porządku). Następnie, gdy odpompowujemy (tj. Przypadek ), otrzymujemy nowy ciąg , a następnie, jeśli mogą być podzielone na , środek musi być gdzieś w drugim części, a więc pierwsza połowaa b v y = a k 1 b k 2 a b v y i = 0 s ′ = a p - k 1 b p - k 2 a p b p s ′ w w a a p - k 1 b p - k 2 a ( k 1 + k 2$vxy$$a$$b$$vy = a^{k_{1}}b^{k_{2}}$$a$$b$$v$$y$$i=0$$s'=a^{p-k_{1}}b^{p-k_{2}}a^{p}b^{p}$$s'$$ww$$a$ a p - ( k 1 + k 2 ) / 2 b p v$a^{p-k_{1}}b^{p-k_{2}}a^{(k_{1}+k_{2})/2}$, a druga połowa to . Oczywiście nie są to te same ciągi, więc nie możemy tam wstawić i .$a^{p-(k_{1}+k_{2})/2}b^{p}$$v$$y$

Pozostałe przypadki powinny być stamtąd dość przejrzyste - są to te same pomysły, po prostu umieszczając i w pozostałych 3 miejscach w pierwszej instancji i 2 miejsca w drugiej instancji. We wszystkich przypadkach można go jednak pompować w taki sposób, że porządkowanie jest wyraźnie pomieszane po podzieleniu łańcucha na pół.$v$$y$

Lemma Ogdena

Lemma (Ogden). Niech będzie językiem bezkontekstowym. Następnie istnieje stała taka, że ​​dla każdego i dowolnego sposobu oznaczania lub większej liczby pozycji (symboli) jako „pozycji wyróżniających”, wówczas można zapisać jako , tak żeN z ∈ L N z z z = u v w x $L$$N$$z\in L$ $N$$z$$z$$z=uvwxy$

1. $vx$ ma co najmniej jedną wyróżnioną pozycję.
2. $vwx$ ma najwyżej wyróżnionych pozycji.$N$
3. Dla wszystkich , .u v i w x i y ∈ $i\geq 0$$uv^iwx^iy\in L$

Przykład. Niech . Załóżmy, że jest pozbawione kontekstu i niech będzie stałą podaną przez lemat Ogdena. Niech (Który należy do ) i załóżmy, że zaznaczamy jako wyróżnione wszystkie pozycje symbolu (tj. Pierwsze pozycji ) . Niech będzie rozkładem spełniającym warunki z lematu Ogdena.L N z = a N b N + N ! c N + 2 N ! L a N z z = u v w x y $L=\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$$L$$N$$z=a^Nb^{N+N!}c^{N+2N!}$$L$$a$$N$$z$$z=uvwxy$$z$

• Jeśli lub zawierają różne symbole, to , ponieważ będą symbole w niewłaściwej kolejności.x u v 2 w x 2 y ∉ $v$$x$$uv^2wx^2y\notin L$
• Przynajmniej jeden z i może zawierać tylko symbole , ponieważ tylko „s wyodrębniono. Zatem jeśli lub , to . Niech. Następnie , co oznacza, że dzieli. Niech . Następnie powinien należeć do . Jednak . Ponieważ ma dokładnie symbole , tox a a x ∈ L ( b ∗ ) x ∈ L ( c ∗ ) v ∈ L ( A + ) p = | v | 1 ≤ p ≤ N p N ! q = N ! / p z ′ = u v 2 q + 1 w x 2 q + 1 y $v$$x$$a$$a$$x\in L(b^*)$$x\in L(c^*)$$v\in L(A^+)$$p=|v|$$1\leq p\leq N$$p$$N!$$q=N!/p$$z'=uv^{2q+1}wx^{2q+1}y$$L$ u w y N - p a z ′ 2 N ! + N a v x c z ′ 2 N ! + N c z ′ ∉ L x ∈ L ( A + ) x ∈ L ( $v^{2q+1}=a^{2pq+p}=a^{2N!+p}$$uwy$$N-p$$a$$z'$ma symbole . Ale zarówno jak i nie mają , więc ma również symbole , co oznacza , a to przeczy lematowi Ogdena. Podobna sprzeczność występuje, jeśli lub . Stwierdzamy, że nie jest kontekstowe.$2N!+N$$a$$v$$x$$c$$z'$$2N!+N$$c$$z'\notin L$$x\in L(A^+)$$x\in L(c^*)$$L$

Ćwiczenie. Używając Lemmy Ogdena, pokaż, że nie jest pozbawiony kontekstu.$L=\{a^ib^jc^kd^{\ell}:i=0\text{ or }j=k=\ell\}$

Pompowanie Lemmy

Jest to szczególny przypadek lematu Ogdena, w którym rozróżnia się wszystkie pozycje.

Lemat. Niech będzie językiem bezkontekstowym. Następnie istnieje stała taka, że ​​dla każdego , można zapisać jako , tak żeN z ∈ L z z = u v w x $L$$N$$z\in L$$z$$z=uvwxy$

1. $|vx|>0$ .
2. $|vwx|\leq N$ .
3. Dla wszystkich , .u v i w x i y ∈ $i\geq 0$$uv^iwx^iy\in L$

Twierdzenie Parikha

To jest nawet bardziej techniczne niż Lemma Ogdena.

Definicja. Niech . Definiujemy przez gdzie jest liczbą wystąpień in .Ψ Σ : Σ ∗ → N n Ψ Σ ( w ) = ( m 1 , … , m n ) , m i a i$\Sigma=\{a_1,\ldots,a_n\}$$\Psi_{\Sigma}:\Sigma^*\to\mathbb{N}^n$

Definicja. Podzbiór z jest nazywany liniowym, jeśli można go zapisać: $S$$\mathbb{N}^n$

Definicja. Podzbiór o nazywa półliniowych , jeżeli jest to związek skończonego zbioru zestawów liniowych.$S$$\mathbb{N}^n$

Twierdzenie (Parikh). Niech będzie językiem nad . Jeśli jest pozbawiony kontekstu, to jest półliniowe.$L$$\Sigma$$L$

$$\Psi_{\Sigma}[L]=\{\Psi_{\Sigma}(w):w\in L\}$$

Ćwiczenie. Korzystając z twierdzenia Parikha, pokaż, że nie jest pozbawione kontekstu.$L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$

Ćwiczenie. Korzystając z twierdzenia Parikha, pokaż, że każdy bezkontekstowy język nad pojedynczym alfabetem jest również regularny.

Właściwości zamknięcia

Raz masz małą kolekcję zakaz języków bezkontekstowych często można użyć właściwości zamknięcia z tak:$\mathrm{CFL}$

Załóżmy . Następnie, poprzez właściwość zamknięcia X (wraz z Y), . Jest to sprzeczne z który wiemy, że trzymamy, dlatego .$L \in \mathrm{CFL}$$L' \in \mathrm{CFL}$$L' \notin \mathrm{CFL}$$L \notin \mathrm{CFL}$

Jest to często krótsze (i często mniej podatne na błędy) niż użycie jednego z innych wyników, które wykorzystują mniejszą wiedzę. Jest to również ogólna koncepcja, którą można zastosować do wszystkich rodzajów obiektów.

Przykład 1: Przecięcie ze zwykłymi językami

Zwracamy uwagę na język regularny określony przez dowolne wyrażenie regularne .$\mathcal L(e)$$e$

Niech . Tak jak$L = \{w \mid w \in \{a,b,c\}^*, |w|_a = |w|_b = |w|_c\}$

$\qquad \displaystyle L \cap \mathcal{L}(a^*b^*c^*) = \{a^nb^nc^n \mid n \in \mathbb{N}\} \notin \mathrm{CFL}$

i jest zamknięty pod skrzyżowaniem ze zwykłymi językami, .$\mathrm{CFL}$$L \notin \mathrm{CFL}$

Przykład 2: (odwrotny) homomorfizm

Niech . Z homomorfizmem$L = \{(ab)^{2n}c^md^{2n-m}(aba)^{n} \mid m,n \in \mathbb{N}\}$

$\qquad \displaystyle \phi(x) = \begin{cases} a &x=a \\ \varepsilon &x=b \\ b &x=c \lor x=d \end{cases}$

mamy$\phi(L) = \{a^{2n}b^{2n}a^{2n} \mid n \in \mathbb{N}\}.$

Teraz z

$\qquad \displaystyle \psi(x) = \begin{cases} aa &x=a \lor x=c \\ bb &x=b \end{cases}\quad\text{and}\quad L_1 = \{x^nb^ny^n \mid x,y \in \{a,c\}\wedge n \in \mathbb{N}\},$

otrzymujemy .$L_1 = \psi^{-1}(\phi(L)))$

Wreszcie, przecinając ze zwykłym językiem otrzymujemy język .$L_1$$L_2 = \mathcal L(a^*b^*c^*)$$L_3 = \{a^n b^n c^n \mid n \in \mathbb{N}\}$

W sumie mamy .$L_3 = L_2 \cap \psi^{-1}(\phi(L))$

Załóżmy teraz, że był pozbawiony kontekstu. Następnie, ponieważ jest zamknięty przeciwko homomorfizmowi, homomorfizmowi odwrotnemu i przecinaniu się z regularnymi zbiorami, jest kontekstu. Ale wiemy (za pomocą Pumping Lemma, jeśli to konieczne), że nie jest kontekstu, więc jest to sprzeczność; pokazaliśmy, że .$L$$\mathrm{CFL}$$L_3$$L_3$$L \notin \mathrm{CFL}$

Interchange Lemma

Interchange Lemma [1] proponuje niezbędny warunek kontekstowy chudości, który jest jeszcze silniejszy niż lemat ogdena . Na przykład można tego użyć

$\qquad \{xyyz \mid x,y,z \in \{a,b,c\}^+\} \notin \mathrm{CFL}$

który jest odporny na wiele innych metod. Oto lemat:

Niech . Następnie istnieje stała taka, że ​​dla dowolnej liczby całkowitej , dowolnego zestawu i dowolnej liczby całkowitej przy istnieje ciągi znaków z$L \in \mathrm{CFL}$$c_L$$n\geq 2$$Q_n \subseteq L_n = L \cap \Sigma^n$$m$$n \geq m \geq 2$$k \geq \frac{|Q_n|}{c_L n^2}$$z_i \in Q_n$

1. $z_i = w_ix_iy_i$ dla ,$i=1,\dots,k$
2. $|w_1| = |w_2| = \dots = |w_k|$,
3. $|y_1| = |y_2| = \dots = |y_k|$,
4. $m \geq |x_1| = |x_2| = \dots = |x_k| > \frac{m}{2}$ i
5. $w_ix_jy_i \in L_n$ dla wszystkich .$(i,j) \in [1..k]^2$

Zastosowanie go oznacza znalezienie i taki sposób, że 1.-4. przytrzymaj, ale 5. jest naruszone. Przykład zastosowania podany w oryginalnym artykule jest bardzo szczegółowy i dlatego został pominięty tutaj.$n,m$$Q_n$

W tej chwili nie mam ogólnodostępnej referencji, a powyższe sformułowanie pochodzi z preprint [1] z 1981 r. Doceniam pomoc w wyszukiwaniu lepszych referencji. Wygląda na to, że ta sama właściwość została (ponownie) odkryta niedawno [2].

Inne niezbędne warunki

Boonyavatana i Slutzki [3] badają kilka warunków podobnych do lemie pompowania i wymiany.

1. „Interchange Lemma” dla języków bezkontekstowych W. Ogdena, RJ Rossa i K. Winklmanna (1985)
2. Wymiana lematów na języki zwykłe i bezkontekstowe T. Yamakami (2008)
3. Lematy wymiany lub pompowania (DI) dla języków bezkontekstowych R. Boonyavatana i G. Slutzki (1988)

Nie ma ogólnej metody, ponieważ zestaw języków bezkontekstowych nie jest częściowo rozstrzygalny (akare). Gdyby istniała ogólna metoda, moglibyśmy użyć jej, aby częściowo zdecydować o tym zestawie.

Sytuacja jest jeszcze gorsza, ponieważ biorąc pod uwagę dwa świetlówki kompaktowe, nie można zdecydować, czy ich przecięcie jest również świetlówką kompaktową.

Odniesienia: Hopcroft i Ullman, „Wprowadzenie do teorii automatów, języków i obliczeń”, 1979.

Silniejszą wersją warunku Ogdena ( OC ) jest

Stan Bader-Moury (BMC)

Język spełnia BMC, jeśli istnieje stała taka, że ​​jeśli i oznaczamy w nim pozycje „wyróżniające” pozycje i pozycje „wykluczone”, , wówczas możemy napisać tak aby:$L\subseteq \Sigma^*$$n$$z \in L$$d(z)$$e(z)$$d(z) > n^{e(z)+1}$$z = uvwxy$

1. e ( v x ) = $d(vx) \geq 1$ i$e(vx) =0$
2. $d(vwx) \leq n^{e(vwx)+1}$ i
3. dla każdego , jest .u v i w x i y $i \geq 0$$uv^iwx^iy$$L$

Mówimy, że język jeśli spełnia warunek Bader-Moury.$L \in BMC(\Sigma)$$L$

Mamy , więc BMC jest ściśle silniejszy niż OC.$CFL(\Sigma) \subset BMC(\Sigma) \subset OC(\Sigma)$

Odnośnik: Bader, C., Moura, A., A Generalization of Ogden's Lemma. JACM 29, nr 2, (1982), 404–407