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

1. ĆWICZENIA 10

Ćwiczenie 1

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

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

ROZWIĄZANIE. We wszystkich przypadkach dowód przeprowadzimy nie wprost zakładając, że język $L$ jest bezkontekstowy, a więc spełnia tezę lematu o pompowaniu.
Punkt 1. Rozważmy słowo $a^n{b}^n{c}^n\in L$, dla $3n\ge N$, gdzie $N$ jest stałą z lematu o pompowaniu. Podobnie jak w przykładzie Uzupelnic lekcja11-w -ex1.1| pokazujemy, że jedyną możliwością rozłożenia słowa $a^n{b}^n{c}^n=u_1{w}_{1}u{w}_2{u}_2$ zgodnym z lematem o pompowaniu jest przyjęcie jako $w_1$ i $w_2$ potęgi jednej z liter $a,b,c$. To wyklucza dla pewnych $i$ przynależność do języka $L$ słów $u_1{w}_1^{i}u{w}_2^i{u}_2$.
Punkt 2. Podobnie jak w punkcie 1 rozważmy szczególne dostatecznie długie słowo z języka $L$, a mianowicie $a^n{b}^{n+1}{c}^{n+2}\in L$ i niech $3n+3\ge N$, gdzie $N$ jest stałą z lematu o pompowaniu. Dalsze rozumowanie jest analogicze jak w punkcie 1.
Punkt 3. Dostatecznie długie słowo $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 $w=a_1...a_n$, to

$w\overleftarrow{w}{a}^{|w|}=\underset{u_1}{\underbrace{a_1...a_k}}\underset{w_1}{\underbrace{a_{k+1}...a_n{a}_n....a_{k+1}}}\underset{u}{\underbrace{a_k...a_1}}\underset{w_2}{\underbrace{a^{2(n-k)}}}\underset{u_2}{\underbrace{a^{2k-n}}}$

dla dowolnego $k$ takiego, że $k<n\le 2k$. Dla $n>M$ ($M$ jest stałą z lematu o pompowaniu) $|w_{1}u{w}_2|>M$. Innej możliwości rozkładu słowa z języka $L$ już nie ma. Dalej postępujemy standardowo.

{.3cm} Wprowadzimy uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Dla słowa $w\in A^{*}$ o długości $n$ dowolną liczbę ze zbioru $\{1,.....,n\}$ nazywamy pozycją w słowie $w$. Ustalając dowolny podzbiór $P\subset \{1,.....,n\}$ będziemy mówić, że w słowie $w$ wyróżniono pozycje ze zbioru $P$.

Lemat 1

(Ogden)

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

1. $w_1{w}_2$ zawiera przynajmniej jedną wyróżnioną pozycję,
2. $w_{1}u{w}_2$ zawiera co najwyżej $M$ wyróżnionych pozycji,
3. $u_1{w}_1^{i}u{w}_2^i{u}_2\in L$ dla $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 $L=\{a^i{b}^j{c}^k:i=j,j=k,k=i\}$ nie jest bezkontekstowy.

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

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

Jeśli $w_2\in b^{*}$ lub $w_2\in a^{*}$ to $w_1\in a^{+}$. Jeśli natomiast $w_2\in a^{+}$, to $w_1\in a^{*}$ (dlaczego?). Rozważmy przypadek, gdy $w_1\in a^{+}$ oraz $w_2\in b^{*}$ (pozostałe przypadki traktowane są analogicznie). Niech $p=|w_1|$. Ponieważ $1\le p\le M$, to $p$ dzieli $M!$. Niech $q=\frac{M!}{p}$. Słowo $z=u_1{w}_1^{2q+1}u{w}_2^{2q+1}{u}_2$ należy do $L$, ale $w_1^{2q+1}=a^{p(2q+1)}=a^{2pq+p}=a^{2M!+p}$. Ponieważ ${\mathrm{♯}}_a{u}_{1}u{u}_2=M-p$, to mamy ${\mathrm{♯}}_{a}z=2M!+p+(M-p)=2M!+M$, ale jednocześnie ${\mathrm{♯}}_{c}z=2M!+M={\mathrm{♯}}_{a}z$. Otrzymaliśmy sprzeczność.

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

Ćwiczenie 3

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

$L\in {{ℒ}}_3\iff L\in {{ℒ}}_2$

Rozwiązanie. Wystarczy udowodnić, że każdy język bezkontekstowy jest regularny. Niech $L\subset \{a{\}}^{*}$ będzie językiem bezkontekstowym. Z lematu o pompowaniu wynika, że $\mathrm{\exists }N,M\ge 1$ takie, że każde słowo $w\in L$ o długości $|w|>N$ można przedstawić w formie $w=u_1{w}_{1}u{w}_2{u}_2$, gdzie $w_{1,}{w}_2,v_1,v_2,u\in A^{*}$ oraz $|w_{1}u{w}_2|\le M$, $w_1{w}_2\ne 1$, $u_1{w}_1^{i}u{w}_2^i{u}_2\in L$ dla $i=0,1,...$
Stąd, że $L\subset \{a{\}}^{*}$ wynika, że $w=a^p{a}^k$ dla pewnego $k\le M$ oraz $a^p(a^k{)}^i\in L$ dla $i=0,1,...$.
Przyjmijmy $n=M!$. Wówczas dla każdego słowa $w\in L$ o długości $|w|>N$ mamy $w(a^n{)}^{*}=w(a^k{)}^{\frac{n}{k}}\subset L\subset \{a{\}}^{*}$.
Dla $i=1,...,n$ oznaczmy przez

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

Jeśli $L_i\ne \mathrm{\varnothing }$, to niech $w_i\in L_i$ będzie słowem o najmniejszej długości. Wówczas

$\mathrm{\forall }w\in L:|w|>Nw\in \bigcup _{i=1}^n{w}_i(a^n{)}^{*}.$

Zatem

$L=\{w\in L:|w|\le p\}\cup \bigcup _{i=1}^n{w}_i(a^n{)}^{*}.$

Ćwiczenie 4

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

ROZWIĄZANIE. Język $L=L_1\cap {\bar{L}}_2$, gdzie
$L_1=\{a^n{b}^n:n\ge 0\}$ jest językiem bezkontekstowym,
$L_2=\{w\in \{a,b{\}}^{*}:|w|=5k\text{dla pewnego}k\ge 0\}$ jest językiem regularnym.
Języki regularne są domknięte ze względu na uzupełnienie, a przecięcie języka bezkontekstowego z regularnm jest językiem bezkontekstowym.

Ćwiczenie 5

Czy gramatyka poprawnych nawiasów $(\{v_0\},\{(,)\},v_0,P),\text{ gdzie}P:v_0\to v_0{v}_0|(v_0)|1$

jest jednoznaczna?

ROZWIĄZANIE. Gramatyka nie jest jednoznaczna. Oto dwie pochodne lewostronne słowa $(())()$:
$v_0\mapsto v_0{v}_0\mapsto (v_0)v_0\mapsto ((v_0))v_0\mapsto (())v_0\mapsto (())(v_0)\mapsto (())()$
$v_0\mapsto v_0{v}_0\mapsto v_0{v}_0{v}_0\mapsto (v_0)v_0{v}_0\mapsto ((v_0))v_0{v}_0\mapsto (())v_0{v}_0\mapsto (())(v_0)v_0\mapsto (())()v_0\mapsto (())()$

Ćwiczenie 6

Określ gramatyki generujące języki

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

Czy gramatyki te są jednoznaczne?

ROZWIĄZANIE.
Język $L_1$ jest generowany przez gramatykę $G_1$ o zbiorze praw
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $a^n{b}^n{c}^n$ ma dwa różne wyprowadzenia. Na przykład dla słowa $abc$ mamy

$v_0\mapsto v_{1}c\mapsto a{v}_{2}bc\mapsto abc$ $v_0\mapsto a{w}_1\mapsto ab{w}_{2}c\mapsto abc$

Język $L_2$ jest generowany przez gramatykę $G_2$ o zbiorze praw
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $G_2$ też nie jest jednoznaczna. Każde słowo w postaci $a^n{b}^n{a}^p{b}^p$ ma dwa różne wyprowadzenia. Natomiast język $L_2$ jest również generowany przez gramatykę $G_3$ o zbiorze praw
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $L_2$ jest jednoznaczny.
Uwaga. Język $L_2$ można rozłożyć na sumę trzech rozłącznych i bezkontekstowych języków.
$L_2=\{a^n{b}^n{a}^p{b}^p:n,p\ge 1\}\cup \{a^n{b}^n{a}^p{b}^q:n,p,q\ge 1,p\ne q\}\cup \{a^n{b}^m{a}^p{b}^p:m,n,p\ge 1,n\ne m\}$.
Gramatyka $G_3$ generuje niezależnie od siebie te trzy zbiory. Rozkładając analogicznie język $L_1$ otrzymujemy
$L_1=\{a^n{b}^n{c}^n:n\ge 0\}\cup \{a^n{b}^n{c}^m:k,m,n\ge 0,n\ne m\}\cup \{a^n{b}^m{c}^m:m,n\ge 0,n\ne m\}$.
Tym razem nie jest to rozkład na sumę języków bezkontekstowych.

Ćwiczenie 7

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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. $w_1=bac$,
2. $w_2=babcab$,
3. $w_3=bcaaca$.

ROZWIĄZANIE $w_1\in ̸L(G)$, $w_2,w_3\in L(G)$.

2. ZADANIA DOMOWE

Ćwiczenie 1

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

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

Ćwiczenie 2

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

Wskazówka

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

Ćwiczenie 3

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

Ćwiczenie 4

Czy gramatyka poprawnych nawiasów

$(\{v_0,v_1\},\{(,)\},v_0,P),\text{ gdzie}P:v_0\to v_1{v}_0|1,v_1\to (v_0)$

rozważana w przykładzie Uzupelnic lekcja9-w-ex1.2| jest jednoznaczna?

Ćwiczenie 5

Określ gramatyki generujące języki

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

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

Ćwiczenie 6

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

1. nieskończny,
2. niepusty.

Ćwiczenie 7

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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. $w_1=cabba$,
2. $w_2=baccab$,
3. $w_3=aabbcc$.