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

Wersja z 10:07, 27 sie 2006

Ćwiczenia 10

Ćwiczenie 1

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

$L = {a^{n} b^{m} c^{k} : k = \max {n, m}},$
$L = {a^{k} b^{n} c^{m} : k < n < m},$
$L = {w \overset{\leftarrow}{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 $3 n ⩾ N$ , gdzie $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 $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 $3 n + 3 ⩾ 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 \overset{\leftarrow}{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 \overset{\leftarrow}{w} a^{| w |} = \underset{u_{1}}{\underset{⏟}{a_{1} . . . a_{k}}} \underset{w_{1}}{\underset{⏟}{a_{k + 1} . . . a_{n} a_{n} . . . . a_{k + 1}}} \underset{u}{\underset{⏟}{a_{k} . . . a_{1}}} \underset{w_{2}}{\underset{⏟}{a^{2 (n - k)}}} \underset{u_{2}}{\underset{⏟}{a^{2 k - n}}}

dla dowolnego $k$ takiego, że $k < n ⩽ 2 k$ . 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.

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 ⩾ 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

$w_{1} w_{2}$ zawiera przynajmniej jedną wyróżnioną pozycję,
$w_{1} u w_{2}$ zawiera co najwyżej $M$ wyróżnionych pozycji,
$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^{2 M! + 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 ⩽ p ⩽ M$ , to $p$ dzieli $M!$ . Niech $q = \frac{M!}{p}$ . Słowo $z = u_{1} w_{1}^{2 q + 1} u w_{2}^{2 q + 1} u_{2}$ należy do $L$ , ale $w_{1}^{2 q + 1} = a^{p (2 q + 1)} = a^{2 p q + p} = a^{2 M! + p}$ . Ponieważ $♯_{a} u_{1} u u_{2} = M - p$ , to mamy $♯_{a} z = 2 M! + p + (M - p) = 2 M! + M$ , ale jednocześnie $♯_{c} z = 2 M! + M = ♯_{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} \Leftrightarrow 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 $\exists N, M ⩾ 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} | ⩽ M$ , $w_{1} w_{2} \neq 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 ⩽ 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} \neq \emptyset$ , to niech $w_{i} \in L_{i}$ będzie słowem o najmniejszej długości. Wówczas

\forall w \in L : | w | > N w \in ⋃_{i = 1}^{n} w_{i} (a^{n})^{*} .

Zatem

L = {w \in L : | w | ⩽ p} \cup ⋃_{i = 1}^{n} w_{i} (a^{n})^{*} .

Ćwiczenie 4

Udowodnij, że język Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{ a^{n}b^{n}:n \;} nie jest wielokrotnością liczby $5}$ jest bezkontekstowy.

Rozwiązanie

Język $L = L_{1} \cap {\overline{L}}_{2}$ , gdzie
$L_{1} = {a^{n} b^{n} : n ⩾ 0}$ jest językiem bezkontekstowym,
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_2=\left\{ w \in \{a,b\}^* : |w|=5k } dla pewnego $k ⩾ 0}$ 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

({v_{0}}, {(,)}, v_{0}, P),

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:

$L_{1} = {a^{n} b^{m} c^{m} : m, n ⩾ 0} \cup {a^{n} b^{n} c^{m} : m, n ⩾ 0}$ ,
$L_{2} = {a^{n} b^{n} a^{p} b^{q} : n, p, q ⩾ 1} \cup {a^{n} b^{m} a^{p} b^{p} : n, m, p ⩾ 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 $a b c$ mamy:

v_{0} \mapsto v_{1} c \mapsto a v_{2} b c \mapsto a b c,

v_{0} \mapsto a w_{1} \mapsto a b w_{2} c \mapsto a b c .

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 ⩾ 1} \cup {a^{n} b^{n} a^{p} b^{q} : n, p, q ⩾ 1, p \neq q} \cup {a^{n} b^{m} a^{p} b^{p} : m, n, p ⩾ 1, n \neq 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 ⩾ 0} \cup {a^{n} b^{n} c^{m} : k, m, n ⩾ 0, n \neq m} \cup {a^{n} b^{m} c^{m} : m, n ⩾ 0, n \neq 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ę:

$w_{1} = b a c$ ,
$w_{2} = b a b c a b$ ,
$w_{3} = b c a a c a$ .

Rozwiązanie

$w_{1} \in̸ L (G)$ , $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:

$L = {a^{n} b^{m} c^{k} : k = m i n {m, n}},$
$L = {a^{n} b^{m} c^{k} : k = m n},$
$L = {a^{n} b^{n^{2}}} .$

Ćwiczenie 9

Stosując lemat Ogdena, pokaż, że język $L = {a^{i} b^{j} c^{k} : i, j, k > 1, k = i r, k = j s,$ 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 10

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

Ćwiczenie 11

Czy gramatyka poprawnych nawiasów

({v_{0}, v_{1}}, {(,)}, v_{0}, P),

gdzie

P : v_{0} \to v_{1} v_{0} | 1, v_{1} \to (v_{0})

rozważana w przykładzie 1.2 jest jednoznaczna?

Ćwiczenie 12

Określ gramatyki generujące języki:

$L_{3} = {a^{n} b^{m} c^{n} d^{p} : m, n, p ⩾ 0} \cup {a^{n} b^{m} c^{p} d^{m} : m, n, p ⩾ 0}$ ,
$L_{4} = {a^{n} b^{2 n} : n ⩾ 1} \cup {a^{n} b^{3 n} : n ⩾ 1}$ .

Czy gramatyki te są jednoznaczne? Wykaż, że język $L_{4}$ jest jednoznaczny.

Ćwiczenie 13

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

nieskończny,
niepusty.

Ćwiczenie 14

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ę:

$w_{1} = c a b b a$ ,
$w_{2} = b a c c a b$ ,
$w_{3} = a a b b c c$ .

@@ Linia 2: / Linia 2: @@
 {{cwiczenie|1||
-Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są bezkontekstowe:
+Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:
-#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=\max \left\{ n,m\right\} \right\}   </math>
+#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=\max \left\{ n,m\right\} \right\},   </math>
-#  <math>\displaystyle L=\left\{ a^{k}b^{n}c^{m}:k<n<m\right\}   </math>
+#  <math>\displaystyle L=\left\{ a^{k}b^{n}c^{m}:k<n<m\right\},  </math>
-#  <math>\displaystyle L=\left\{ w\overleftarrow{w}a^{|w|}:w\in \left\{ a,b\right\} ^{*}\right\}   </math>
+#  <math>\displaystyle L=\left\{ w\overleftarrow{w}a^{|w|}:w\in \left\{ a,b\right\} ^{*}\right\}.  </math>
 }}
@@ Linia 26: / Linia 26: @@
 Punkt 3.<br>
 Dostatecznie długie słowo <math>\displaystyle  w\overleftarrow{w}a^{|w|}\in L</math> możemy rozłożyć na katenację pięciu słów
-tak by był spełniony  warunek pompowania z lematu. Jeśli <math>\displaystyle w=a_1...a_n</math>, to
+tak, by był spełniony  warunek pompowania z lematu. Jeśli <math>\displaystyle w=a_1...a_n</math>, to
 <center><math>\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}</math></center>
@@ Linia 35: / Linia 35: @@
 Wprowadzimy uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Dla słowa <math>\displaystyle w \in A^*</math>
 o długości <math>\displaystyle n</math> dowolną liczbę ze zbioru <math>\displaystyle \{1,.....,n\}</math> nazywamy pozycją w słowie <math>\displaystyle w</math>. Ustalając
-dowolny podzbiór <math>\displaystyle P \subset \{1,.....,n\}</math> będziemy mówić, że w słowie <math>\displaystyle w</math> wyróżniono pozycje ze zbioru <math>\displaystyle P</math>.
+dowolny podzbiór <math>\displaystyle P \subset \{1,.....,n\}</math>, będziemy mówić, że w słowie <math>\displaystyle w</math> wyróżniono pozycje ze zbioru <math>\displaystyle P</math>.
 </div></div>
@@ Linia 90: / Linia 90: @@
 {{cwiczenie|3||
 Udowodnij, że dla dowolnego języka <math>\displaystyle L</math> nad alfabetem jednoelementowym
-<center><math>\displaystyle L \in \mathcal{L}_3 \Leftrightarrow L \in \mathcal{L}_2</math></center>
+<center><math>\displaystyle L \in \mathcal{L}_3 \Leftrightarrow L \in \mathcal{L}_2.</math></center>
 }}
@@ Linia 104: / Linia 104: @@
 <math>\displaystyle w(a^n)^*=w(a^k)^{\frac{n}{k}}\subset L \subset \{a\}^*</math>. <br>
 Dla <math>\displaystyle i=1,...,n</math> oznaczmy przez
-<center><math>\displaystyle L_i = a^{p+i}(a^n)^* \cap L</math></center>
+<center><math>\displaystyle L_i = a^{p+i}(a^n)^* \cap L.</math></center>
 Jeśli <math>\displaystyle L_i \neq \emptyset</math>, to niech <math>\displaystyle w_i \in L_i</math> będzie słowem o najmniejszej długości. Wówczas
@@ Linia 122: / Linia 122: @@
 <math>\displaystyle L_1=\left\{ a^{n}b^{n}:n\geqslant 0\right\}   </math>     jest językiem bezkontekstowym,<br>
 <math>\displaystyle L_2=\left\{ w \in \{a,b\}^* : |w|=5k </math> dla pewnego <math> k\geqslant 0 \rbrace  </math>  jest językiem regularnym.<br>
-Języki regularne są domknięte ze względu na uzupełnienie, a przecięcie języka bezkontekstowego z regularnm jest
+Języki regularne są domknięte ze względu na uzupełnienie, a przecięcie języka bezkontekstowego z regularnym jest
 językiem bezkontekstowym.
 </div></div>
@@ Linia 138: / Linia 138: @@
 <math>\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 (())() </math>
+(())()v_0 \mapsto (())(). </math>
 </div></div>
 {{cwiczenie|6||
-Określ gramatyki generujące języki
+Określ gramatyki generujące języki:
 # <math>\displaystyle L_1 =\{a^n b^m c^m : m,n \geqslant 0 \} \cup \{a^n b^n c^m : m,n \geqslant 0 \} </math>,
 # <math>\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 \}</math>.
@@ Linia 153: / Linia 153: @@
 <math>\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</math><br>
+w_1 \rightarrow aw_1 \; |\; bw_2 c \; |\;1,\;\; w_2 \rightarrow  bw_2 c \; |\;1.</math><br>
 Gramatyka ta nie jest jednoznaczna. Każde słowo w postaci <math>\displaystyle a^nb^nc^n</math> ma dwa różne wyprowadzenia.
-Na przykład dla słowa <math>\displaystyle abc</math> mamy
+Na przykład dla słowa <math>\displaystyle abc</math> mamy:
-<center><math>\displaystyle v_0 \mapsto v_1c \mapsto av_2bc \mapsto abc  </math></center>
+<center><math>\displaystyle v_0 \mapsto v_1c \mapsto av_2bc \mapsto abc,  </math></center>
-<center><math>\displaystyle v_0 \mapsto aw_1 \mapsto abw_2c \mapsto abc  </math></center>
+<center><math>\displaystyle v_0 \mapsto aw_1 \mapsto abw_2c \mapsto abc.  </math></center>
 Język <math>\displaystyle L_2</math> jest  generowany przez  gramatykę <math>\displaystyle G_2</math>  o zbiorze praw<br>
@@ Linia 164: / Linia 164: @@
 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</math><br>
+v_5 \rightarrow av_5 b \; |\; ab ,\;\; v_6 \rightarrow  a v_6 b \; |\;ab.</math><br>
 Gramatyka <math>\displaystyle G_2</math> też nie jest jednoznaczna. Każde słowo w postaci <math>\displaystyle a^n b^n a^p b^p</math> ma dwa różne wyprowadzenia.
 Natomiast język <math>\displaystyle L_2</math> jest również generowany przez gramatykę  <math>\displaystyle G_3</math>
@@ Linia 170: / Linia 170: @@
 <math>\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,        \;\;
+v_4  \rightarrow   v_4 b  \; |\;v_1 b        \;\;
 </math><br>
 i ta gramatyka jest jednoznaczna, co oznacza, że język <math>\displaystyle L_2</math> jest jednoznaczny.<br>
@@ Linia 176: / Linia 176: @@
 <math>\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  \}</math>.<br>
-Gramatyka <math>\displaystyle G_3</math> generuje niezależnie od siebie te trzy zbiory. Rozkładając analogicznie język <math>\displaystyle L_1</math> otrzymujemy<br>
+Gramatyka <math>\displaystyle G_3</math> generuje niezależnie od siebie te trzy zbiory. Rozkładając analogicznie język <math>\displaystyle L_1</math>, otrzymujemy:<br>
 <math>\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  \}</math>.<br>
@@ Linia 192: / Linia 192: @@
 \endaligned</math></center>
-Używając algorytmu Cocke'a-Youngera-Kasamiego sprawdź, czy poniższe
+Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe
-słowa należą do języka generowanego przez tę gramatykę.
+słowa należą do języka generowanego przez tę gramatykę:
 # <math>\displaystyle w_1=bac</math>,
 # <math>\displaystyle w_2=babcab</math>,
@@ Linia 207: / Linia 207: @@
 {{cwiczenie|8||
-Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są bezkontekstowe:
+Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:
-#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=min\{m,n\}\right\}   </math>
+#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=min\{m,n\}\right\},   </math>
-#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=mn\right\}   </math>
+#  <math>\displaystyle L=\left\{ a^{n}b^{m}c^{k}:k=mn\right\},   </math>
-#  <math>\displaystyle L=\left\{ a^{n}b^{n^{2}}\right\}   </math>
+#  <math>\displaystyle L=\left\{ a^{n}b^{n^{2}}\right\}.   </math>
 }}
 {{cwiczenie|9||
-Stosując lemat Ogdena pokaż, że język <math>\displaystyle L=\{a^ib^jc^k: i,j,k>1,\ k
+Stosując lemat Ogdena, pokaż, że język <math>\displaystyle L=\{a^ib^jc^k: i,j,k>1,\ k
 \not = ir,\ k \not = js, </math> gdzie <math>\displaystyle r,s \in \{2,3,...\}\}</math> nie jest
 bezkontekstowy.
@@ Linia 239: / Linia 239: @@
 {{cwiczenie|12||
-Określ gramatyki generujące języki
+Określ gramatyki generujące języki:
 # <math>\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 \} </math>,
 # <math>\displaystyle L_4 =\{a^n b^{2n} : n \geqslant 1 \}\cup \{a^n b^{3n} : n \geqslant 1 \}</math>.
@@ Linia 247: / Linia 247: @@
 {{cwiczenie|13||
-Napisz algorytmy rozstrzygające, czy dany język bezkontekstowy jest
+Napisz algorytmy rozstrzygające, czy dany język bezkontekstowy jest:
 # nieskończny,
 # niepusty.
@@ Linia 263: / Linia 263: @@
 \endaligned</math></center>
-Używając algorytmu Cocke'a-Youngera-Kasamiego sprawdź, czy poniższe
+Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe
-słowa należą do języka generowanego przez tę gramatykę.
+słowa należą do języka generowanego przez tę gramatykę:
 # <math>\displaystyle w_1=cabba</math>,
 # <math>\displaystyle w_2=baccab</math>,

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

Wersja z 10:07, 27 sie 2006

Ćwiczenia 10

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia