Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne

From Studia Informatyczne

Ćwiczenia 10

Ćwiczenie 1

Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:

  1. \displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=\max \left\{ n,m\right\} \right\},
  2. \displaystyle L=\left\{ a^{k}b^{n}c^{m}:k<n<m\right\},
  3. \displaystyle L=\left\{ w\overleftarrow{w}a^{|w|}:w\in \left\{ a,b\right\} ^{*}\right\}.

Rozwiązanie

We wszystkich przypadkach dowód przeprowadzimy nie wprost zakładając, że język \displaystyle L jest bezkontekstowy, a więc spełnia tezę lematu o pompowaniu.

Punkt 1.

Rozważmy słowo \displaystyle  a^{n}b^{n}c^n \in L, dla \displaystyle 3n \geqslant N, gdzie \displaystyle N jest stałą z lematu o pompowaniu. Podobnie jak w przykładzie 1.1 pokazujemy, że jedyną możliwością rozłożenia słowa \displaystyle  a^{n}b^{n}c^n = u_1w_1uw_2u_2 zgodnym z lematem o pompowaniu jest przyjęcie jako \displaystyle w_1 i \displaystyle w_2 potęgi jednej z liter \displaystyle a,b,c. To wyklucza dla pewnych \displaystyle i przynależność do języka \displaystyle L słów \displaystyle   u_1w_1^i uw_2^iu_2.

Punkt 2.

Podobnie jak w punkcie 1 rozważmy szczególne dostatecznie długie słowo z języka \displaystyle L, a mianowicie \displaystyle a^{n}b^{n+1}c^{n+2} \in L i niech \displaystyle 3n+3 \geqslant N, gdzie \displaystyle N jest stałą z lematu o pompowaniu. Dalsze rozumowanie jest analogicze jak w punkcie 1.

Punkt 3.

Dostatecznie długie słowo \displaystyle  w\overleftarrow{w}a^{|w|}\in L możemy rozłożyć na katenację pięciu słów tak, by był spełniony warunek pompowania z lematu. Jeśli \displaystyle w=a_1...a_n, to

\displaystyle w\overleftarrow{w}a^{|w|}=\underbrace {a_1...a_k}_{u_1} \underbrace{a_{k+1}...a_n a_n....a_{k+1}}_{w_1 } \underbrace{a_k ...a_1}_u \underbrace{a^{2(n-k)}}_{w_2} \underbrace{a^{2k-n}} _{u_2}

dla dowolnego \displaystyle k takiego, że \displaystyle k<n\leqslant 2k. Dla \displaystyle n> M (\displaystyle M jest stałą z lematu o pompowaniu) \displaystyle |w_1 uw_2|>M. Innej możliwości rozkładu słowa z języka \displaystyle L już nie ma. Dalej postępujemy standardowo.

Wprowadzimy uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Dla słowa \displaystyle w \in A^*

o długości \displaystyle n dowolną liczbę ze zbioru \displaystyle \{1,.....,n\} nazywamy pozycją w słowie \displaystyle w. Ustalając dowolny podzbiór \displaystyle P \subset \{1,.....,n\}, będziemy mówić, że w słowie \displaystyle w wyróżniono pozycje ze zbioru \displaystyle P.

Lemat 1 (Ogden)

Dla dowolnego języka bezkontekstowego \displaystyle L \subset A^* istnieje liczba naturalna \displaystyle M \geqslant 1 taka, że każde słowo \displaystyle w \in L, w którym wyróżniono \displaystyle M lub więcej pozycji, można przedstawić w formie \displaystyle w=u_1w_1uw_2u_2, gdzie \displaystyle w_{1,}w_{2},v_{1},v_{2},u\in A^{*} oraz

  1. \displaystyle w_1w_2 zawiera przynajmniej jedną wyróżnioną pozycję,
  2. \displaystyle w_1uw_2 zawiera co najwyżej \displaystyle M wyróżnionych pozycji,
  3. \displaystyle u_1w_1^iuw_2^iu_2 \in L dla \displaystyle i=0,1,...

Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena. Lemat Ogdena można próbować stosować w tych przypadkach, w których lemat o pompowaniu nie działa.

Ćwiczenie 2

Stosując lemat Ogdena pokaż, że język \displaystyle L=\{a^ib^jc^k: i \not = j, j  \not = k, k \not = i\} nie jest bezkontekstowy.

Rozwiązanie

Nie wprost, załóżmy, że \displaystyle L jest bezkontekstowy i niech \displaystyle M będzie stałą z lematu Ogdena. Rozważmy słowo \displaystyle w=a^Mb^{M!+M}c^{2M!+M}. Wyróżnijmy wszystkie pozycje, na których znajdują się litery \displaystyle a.

Weźmy rozkład \displaystyle w=u_1w_1uw_2u_2. Zauważmy, że jeśli w \displaystyle w_1 lub \displaystyle w_2 występują co najmniej dwie różne litery, to \displaystyle w \not \in L (np. jeśli \displaystyle w_1 składa się z liter \displaystyle a i \displaystyle b to w słowie \displaystyle w_1^2 przynajmniej jedna litera \displaystyle a znajdzie się za jakąś literą \displaystyle b). Ponieważ zaznaczyliśmy pozycje liter \displaystyle a, to z założenia lematu musi

być \displaystyle w_1 \in a^+ lub \displaystyle w_2 \in a^+.

Jeśli \displaystyle w_2 \in b^* lub \displaystyle w_2 \in a^* to \displaystyle w_1 \in a^+. Jeśli natomiast \displaystyle w_2 \in a^+, to \displaystyle w_1 \in a^* (dlaczego?).

Rozważmy przypadek, gdy \displaystyle w_1 \in a^+ oraz \displaystyle w_2 \in b^* (pozostałe przypadki traktowane są analogicznie). Niech \displaystyle p=|w_1|. Ponieważ \displaystyle 1 \leqslant p  \leqslant M, to \displaystyle p dzieli \displaystyle M!. Niech \displaystyle q=\frac{M!}{p}. Słowo \displaystyle z=u_1w_1^{2q+1}uw_2^{2q+1}u_2 należy do \displaystyle L, ale \displaystyle w_1^{2q+1}=a^{p(2q+1)}=a^{2pq+p}=a^{2M!+p}. Ponieważ \displaystyle \sharp_a  u_1uu_2=M-p, to mamy \displaystyle \sharp_a z = 2M!+p+(M-p)=2M!+M, ale jednocześnie \displaystyle \sharp_c z = 2M!+M = \sharp_a z. Otrzymaliśmy sprzeczność.

W pozostałych przypadkach w analogiczny sposób dochodzimy do takiej sprzeczności. Zatem \displaystyle L nie jest bezkontekstowy.

Ćwiczenie 3

Udowodnij, że dla dowolnego języka \displaystyle L nad alfabetem jednoelementowym

\displaystyle L \in \mathcal{L}_3 \Leftrightarrow L \in \mathcal{L}_2.

Rozwiązanie

Wystarczy udowodnić, że każdy język bezkontekstowy jest regularny. Niech \displaystyle  L \subset \{a\}^* będzie językiem bezkontekstowym. Z lematu o pompowaniu wynika, że \displaystyle \exists N,M \geqslant 1 takie, że każde słowo \displaystyle w \in L o długości \displaystyle |w| > N można przedstawić w formie \displaystyle w=u_1w_1uw_2u_2, gdzie \displaystyle w_{1,}w_{2},v_{1},v_{2},u\in A^{*} oraz \displaystyle |w_1uw_2 |\leqslant M, \displaystyle w_1w_2 \neq 1, \displaystyle u_1w_1^iuw_2^iu_2 \in L dla \displaystyle i=0,1,...
Stąd, że \displaystyle  L \subset \{a\}^* wynika, że \displaystyle w=a^pa^k dla pewnego \displaystyle k\leqslant M oraz \displaystyle a^p(a^k)^i \in L dla \displaystyle i=0,1,....
Przyjmijmy \displaystyle n=M!. Wówczas dla każdego słowa \displaystyle w \in L o długości \displaystyle |w| > N mamy \displaystyle w(a^n)^*=w(a^k)^{\frac{n}{k}}\subset L \subset \{a\}^*.
Dla \displaystyle i=1,...,n oznaczmy przez

\displaystyle L_i = a^{p+i}(a^n)^* \cap L.

Jeśli \displaystyle L_i \neq \emptyset, to niech \displaystyle w_i \in L_i będzie słowem o najmniejszej długości. Wówczas

\displaystyle \forall w \in L:|w|>N \;\;w \in \bigcup_{i=1}^n w_i(a^n)^*.
Zatem
\displaystyle L=\{w \in L : |w|\leqslant p\} \cup \bigcup_{i=1}^n w_i(a^n)^*.

Ćwiczenie 4

Udowodnij, że język \displaystyle L=\left\{ a^{n}b^{n}:n \; nie jest wielokrotnością liczby 5 \rbrace jest bezkontekstowy.

Rozwiązanie

Język \displaystyle L=L_1 \cap \overline{L}_2, gdzie
\displaystyle L_1=\left\{ a^{n}b^{n}:n\geqslant 0\right\} jest językiem bezkontekstowym,
\displaystyle L_2=\left\{ w \in \{a,b\}^* : |w|=5k dla pewnego k\geqslant 0 \rbrace jest językiem regularnym.
Języki regularne są domknięte ze względu na uzupełnienie, a przecięcie języka bezkontekstowego z regularnym jest językiem bezkontekstowym.

Ćwiczenie 5

Czy gramatyka poprawnych nawiasów
\displaystyle (\{v_0\},\{(,)\},v_0, P ), gdzie P: v_0 \rightarrow v_0 v_0\;|\;(v_0)\;|\;1

jest jednoznaczna?

Rozwiązanie

Gramatyka nie jest jednoznaczna. Oto dwie pochodne lewostronne słowa \displaystyle (())():
\displaystyle v_0\mapsto v_0v_0 \mapsto (v_0)v_0 \mapsto ((v_0))v_0\mapsto (())v_0 \mapsto (())(v_0) \mapsto (())()
\displaystyle v_0\mapsto v_0v_0 \mapsto v_0v_0 v_0 \mapsto (v_0)v_0v_0 \mapsto ((v_0))v_0v_0  \mapsto (())v_0v_0  \mapsto (())(v_0) v_0 \mapsto (())()v_0 \mapsto (())().

Ćwiczenie 6

Określ gramatyki generujące języki:

  1. \displaystyle L_1 =\{a^n b^m c^m : m,n \geqslant 0 \} \cup \{a^n b^n c^m : m,n \geqslant 0 \},
  2. \displaystyle L_2 =\{a^n b^n a^p b^q : n,p,q \geqslant 1 \}\cup \{a^n b^m a^p b^p : n,m,p \geqslant 1 \}.

Czy gramatyki te są jednoznaczne?

Rozwiązanie

Język \displaystyle L_1 jest generowany przez gramatykę \displaystyle G_1 o zbiorze praw
\displaystyle  P_1 : v_0 \rightarrow v_1c \; |\; a w_1 \; |\;av_2 b\; |\; 1  ,\;\;  v_1 \rightarrow v_1c \; |\;av_2 b \; |\;1 , \;\; v_2 \rightarrow a v_2 b \; |\;1 ,\\ w_1 \rightarrow aw_1 \; |\; bw_2 c \; |\;1,\;\; w_2 \rightarrow  bw_2 c \; |\;1.
Gramatyka ta nie jest jednoznaczna. Każde słowo w postaci \displaystyle a^nb^nc^n ma dwa różne wyprowadzenia. Na przykład dla słowa \displaystyle abc mamy:

\displaystyle v_0 \mapsto v_1c \mapsto av_2bc \mapsto abc,
\displaystyle v_0 \mapsto aw_1 \mapsto abw_2c \mapsto abc.

Język \displaystyle L_2 jest generowany przez gramatykę \displaystyle G_2 o zbiorze praw
\displaystyle  P_2 : v_0 \rightarrow v_1 \; |\; v_2 ,    \;\;   v_1 \rightarrow av_1 \; |\;av_3    , \;\; v_2 \rightarrow  v_2 b \; |\;v_4 b , \;\;  v_3 \rightarrow bv_3    \; |\; bv_5, \\ v_4  \rightarrow   v_4 a  \; |\;v_6 a,        \;\; v_5 \rightarrow av_5 b \; |\; ab ,\;\; v_6 \rightarrow  a v_6 b \; |\;ab.
Gramatyka \displaystyle G_2 też nie jest jednoznaczna. Każde słowo w postaci \displaystyle a^n b^n a^p b^p ma dwa różne wyprowadzenia. Natomiast język \displaystyle L_2 jest również generowany przez gramatykę \displaystyle G_3 o zbiorze praw
\displaystyle  P_3 : v_0 \rightarrow v_1 v_1\; |\; v_1 v_2 \; |\; v_2 v_1,    \;\;   v_1 \rightarrow av_1b \; |\;ab    , \;\; v_2 \rightarrow  av_3 \; |\;v_4 b , \;\;  v_3 \rightarrow av_3    , \\ v_4  \rightarrow   v_4 b  \; |\;v_1 b        \;\;
i ta gramatyka jest jednoznaczna, co oznacza, że język \displaystyle L_2 jest jednoznaczny.
Uwaga. Język \displaystyle L_2 można rozłożyć na sumę trzech rozłącznych i bezkontekstowych języków.
\displaystyle L_2 = \{a^n b^n a^p b^p : n,p \geqslant 1\}\cup \{a^n b^n a^p b^q : n,p,q \geqslant 1,  \;p\neq q \}\cup  \{a^n b^m a^p b^p : m,n,p \geqslant 1, n\neq m  \}.
Gramatyka \displaystyle G_3 generuje niezależnie od siebie te trzy zbiory. Rozkładając analogicznie język \displaystyle L_1, otrzymujemy:
\displaystyle L_1 =\{a^n b^n c^n : n \geqslant 0 \} \cup \{a^n b^n c^m : k,m,n \geqslant 0, n\neq m  \}\cup \{a^n b^m c^m : m,n \geqslant 0, n\neq m  \}.
Tym razem nie jest to rozkład na sumę języków bezkontekstowych.

Ćwiczenie 7

Dana niech będzie gramatyka (\displaystyle v_0 jest symbolem początkowym):

\displaystyle \aligned v_0 & \rightarrow & v_0v_1\ |\ v_3v_1 \\ v_1 & \rightarrow & v_1v_2\ |\ v_2v_3 \\ v_2 & \rightarrow & v_4v_1\ |\ v_3v_3\ |\ a \\ v_3 & \rightarrow & v_1v_2\ |\ v_4v_2\ |\ b \\ v_4 & \rightarrow & v_3v_4\ |\ v_0v_1\ |\ c \endaligned

Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe słowa należą do języka generowanego przez tę gramatykę:

  1. \displaystyle w_1=bac,
  2. \displaystyle w_2=babcab,
  3. \displaystyle w_3=bcaaca.

Rozwiązanie

\displaystyle w_1 \not \in L(G), \displaystyle w_2, w_3 \in L(G).

ZADANIA DOMOWE

Ćwiczenie 8

Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:

  1. \displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=min\{m,n\}\right\},
  2. \displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=mn\right\},
  3. \displaystyle L=\left\{ a^{n}b^{n^{2}}\right\}.

Ćwiczenie 9

Stosując lemat Ogdena, pokaż, że język \displaystyle L=\{a^ib^jc^k: i,j,k>1,\ k  \not = ir,\ k \not = js, gdzie \displaystyle r,s \in \{2,3,...\}\} nie jest bezkontekstowy.

Wskazówka

Rozważ słowo \displaystyle a^Pb^Pc^{(P-1)!}, gdzie \displaystyle P jest liczbą pierwszą większą niż \displaystyle M+1 i większą niż 3, gdzie \displaystyle M jest stałą z lematu. Jako pozycje oznaczone wybierz wszystkie pozycje liter \displaystyle c.

Ćwiczenie 10

Udowodnij, że język \displaystyle L=\left\{ w\overleftarrow{w } : w \in \{a,b\}^* \setminus \{ab^2a\} \right\} jest bezkontekstowy.

Ćwiczenie 11

Czy gramatyka poprawnych nawiasów

\displaystyle (\{v_0,v_1\},\{(,)\},v_0, P ), gdzie P: v_0 \rightarrow v_1 v_0\;|\;1, \;\; v_1 \rightarrow (v_0)

rozważana w przykładzie 1.2 jest jednoznaczna?

Ćwiczenie 12

Określ gramatyki generujące języki:

  1. \displaystyle L_3 =\{a^n b^m c^nd^p : m,n,p \geqslant 0 \} \cup \{a^n b^m c^p d^m : m,n,p \geqslant 0 \},
  2. \displaystyle L_4 =\{a^n b^{2n} : n \geqslant 1 \}\cup \{a^n b^{3n} : n \geqslant 1 \}.

Czy gramatyki te są jednoznaczne? Wykaż, że język \displaystyle L_4 jest jednoznaczny.

Ćwiczenie 13

Napisz algorytmy rozstrzygające, czy dany język bezkontekstowy jest:

  1. nieskończny,
  2. niepusty.

Ćwiczenie 14

Dana niech będzie gramatyka (\displaystyle v_0 jest symbolem początkowym):

\displaystyle \aligned v_0 & \rightarrow & v_0v_1\ |\ v_3v_1 \\ v_1 & \rightarrow & v_2v_1\ |\ v_3v_2 \\ v_2 & \rightarrow & v_1v_4\ |\ v_3v_3\ |\ a \\ v_3 & \rightarrow & v_2v_2\ |\ v_4v_2\ |\ b \\ v_4 & \rightarrow & v_1v_4\ |\ v_0v_1\ |\ c. \endaligned

Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe słowa należą do języka generowanego przez tę gramatykę:

  1. \displaystyle w_1=cabba,
  2. \displaystyle w_2=baccab,
  3. \displaystyle w_3=aabbcc.