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

Aktualna wersja na dzień 21:58, 15 wrz 2023

Ć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, \dots, 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 $L = {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,
$L_{2} = {w \in {a, b}^{*} : | w | = 5 k 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
$\begin{aligned} P_{1} : v_{0} \to v_{1} c | a w_{1} | a v_{2} b | 1, v_{1} \to v_{1} c | a v_{2} b | 1, v_{2} \to a v_{2} b | 1, \\ w_{1} \to a w_{1} | b w_{2} c | 1, w_{2} \to b w_{2} c | 1 . \end{aligned}$
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
$\begin{aligned} P_{2} : v_{0} \to v_{1} | v_{2}, v_{1} \to a v_{1} | a v_{3}, v_{2} \to v_{2} b | v_{4} b, v_{3} \to b v_{3} | b v_{5}, \\ v_{4} \to v_{4} a | v_{6} a, v_{5} \to a v_{5} b | a b, v_{6} \to a v_{6} b | a b . \end{aligned}$
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
$\begin{aligned} P_{3} : v_{0} \to v_{1} v_{1} | v_{1} v_{2} | v_{2} v_{1}, v_{1} \to a v_{1} b | a b, v_{2} \to a v_{3} | v_{4} b, v_{3} \to a v_{3}, \\ v_{4} \to v_{4} b | v_{1} b \end{aligned}$
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):

\begin{aligned} v_{0} & \to & v_{0} v_{1} | v_{3} v_{1} \\ v_{1} & \to & v_{1} v_{2} | v_{2} v_{3} \\ v_{2} & \to & v_{4} v_{1} | v_{3} v_{3} | a \\ v_{3} & \to & v_{1} v_{2} | v_{4} v_{2} | b \\ v_{4} & \to & v_{3} v_{4} | v_{0} v_{1} | c \end{aligned}

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

\begin{aligned} v_{0} & \to & v_{0} v_{1} | v_{3} v_{1} \\ v_{1} & \to & v_{2} v_{1} | v_{3} v_{2} \\ v_{2} & \to & v_{1} v_{4} | v_{3} v_{3} | a \\ v_{3} & \to & v_{2} v_{2} | v_{4} v_{2} | b \\ v_{4} & \to & v_{1} v_{4} | v_{0} v_{1} | c . \end{aligned}

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$ .

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

Aktualna wersja na dzień 21:58, 15 wrz 2023

Ćwiczenia 10

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-{Automat ze stosem.Gramatyki bezkontekstowe i automaty ze stosem.}
+==Ćwiczenia 10==
-==ĆWICZENIA 11==
+{{cwiczenie|1||
+Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:
+#  <math>L=\left\{ a^{n}b^{m}c^{k}:k=\max \left\{ n,m\right\} \right\}</math>
+#  <math>L=\left\{ a^{k}b^{n}c^{m}:k<n<m\right\}</math>
+#  <math>L=\left\{ w\overleftarrow{w}a^{|w|}:w\in \left\{ a,b\right\} ^{*}\right\}</math>
-{{cwiczenie|||
+}}
-Określ automaty ze stosem akceptujące następujące  języki. Ustal czy akceptacja jest przez pusty stos
-czy przez stany końcowe. Czy język <math>\displaystyle L</math> jest deterministyczny?
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-#  <math>\displaystyle L_1=\{a^{n}b^{n+m}a^{m}:\: m,n\geq 1\}  </math>
+We wszystkich przypadkach dowód przeprowadzimy nie wprost zakładając, że język <math>L</math> jest
-#  <math>\displaystyle L_2=\left\{ w\overleftarrow{w} : w \in \{ a,b\}^*  \right\}   </math>
+bezkontekstowy, a więc spełnia tezę lematu o pompowaniu.<br>
-#  <math>\displaystyle L_3=\{a^{n}b^m:\:  1\leq n\leq m\}  </math>
-#  <math>\displaystyle L_4=\{w \in \{ a,b\}^+ :\#_a w = \#_b w \}  </math>
+Punkt 1.<br>
+Rozważmy słowo <math>a^{n}b^{n}c^n \in L</math>, dla  <math>3n \geqslant N</math>, gdzie <math>N</math> jest stałą z lematu o pompowaniu.
+Podobnie jak w przykładzie [http://osilek.mimuw.edu.pl/index.php?title=J%C4%99zyki%2C_automaty_i_obliczenia/Wyk%C5%82ad_10:_Lemat_o_pompowaniu_dla_j%C4%99zyk%C3%B3w_bezkontekstowych._W%C5%82asno%C5%9Bci_j%C4%99zyk%C3%B3w_bezkontekstowych._Problemy_rozstrzygalne#prz.1 1.1]  pokazujemy, że jedyną możliwością rozłożenia
+słowa <math>a^{n}b^{n}c^n = u_1w_1uw_2u_2</math> zgodnym z lematem o pompowaniu jest przyjęcie jako   <math>w_1</math> i <math>w_2</math> potęgi
+jednej z liter <math>a,b,c</math>. To wyklucza dla pewnych <math>i</math> przynależność do języka <math>L</math> słów <math>u_1w_1^i uw_2^iu_2</math>.<br>
+Punkt 2.<br>
+Podobnie jak w punkcie 1 rozważmy szczególne dostatecznie długie słowo z języka <math>L</math>, a mianowicie
+<math>a^{n}b^{n+1}c^{n+2} \in L</math> i niech <math>3n+3 \geqslant N</math>, gdzie <math>N</math> jest stałą z lematu o pompowaniu. Dalsze rozumowanie
+jest analogicze jak w punkcie 1.<br>
-}}
+Punkt 3.<br>
+Dostatecznie długie słowo <math>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>w=a_1...a_n</math>, to
+<center><math>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>
-Wszystkie rozważane automaty będą określone grafem, niemniej dla większej czytelności podamy również alfabet stosu.
+dla dowolnego <math>k</math> takiego, że <math>k<n\leqslant 2k</math>. Dla <math>n> M</math> (<math>M</math> jest stałą z lematu o pompowaniu) <math>|w_1 uw_2|>M</math>.
+Innej możliwości rozkładu słowa z języka <math>L</math> już nie ma. Dalej postępujemy standardowo.
-ROZWIĄZANIE   punktu 1.
+Wprowadzimy uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Dla słowa <math>w \in A^*</math>
-Szukany automat  określony  jest rysunkiem <br>
+o długości <math>n</math> dowolną liczbę ze zbioru <math>\{1,.....,n\}</math> nazywamy pozycją w słowie <math>w</math>. Ustalając
+dowolny podzbiór <math>P \subset \{1,.....,n\}</math>, będziemy mówić, że w słowie <math>w</math> wyróżniono pozycje ze zbioru <math>P</math>.
+</div></div>
-rys 1   ja-lekcja11-c-rys1 <br>
+{{lemat|1 (Ogden)||
-gdzie <math>\displaystyle A_S = \{z_0,a,b\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu.
+Dla dowolnego języka bezkontekstowego <math>L \subset A^*</math> istnieje
-Zauważ, że automat ten akceptuje język <math>\displaystyle L_1</math> zarówno przez stany końcowe jak i przez pusty stos.
+liczba naturalna <math>M \geqslant 1</math> taka, że każde słowo <math>w \in L</math>, w którym
-Automat jest deterministyczny, a to oznacza, że język <math>\displaystyle L_1</math> jest też deterministyczny.<br>
+wyróżniono <math>M</math> lub więcej pozycji, można przedstawić w formie
-ROZWIĄZANIE   punktu 2.<br>
+<math>w=u_1w_1uw_2u_2</math>, gdzie  <math>w_{1,}w_{2},v_{1},v_{2},u\in A^{*}</math>
-Szukany automat  określony  jest rysunkiem <br>
+oraz
+# <math>w_1w_2</math> zawiera przynajmniej jedną wyróżnioną pozycję,
+# <math>w_1uw_2</math> zawiera co najwyżej <math>M</math> wyróżnionych pozycji,
+# <math>u_1w_1^iuw_2^iu_2 \in L</math> dla <math>i=0,1,.</math>.
-rys 2     ja-lekcja11-c-rys2  <br>
+}}
-gdzie <math>\displaystyle A_S = \{z_0,a,b\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu i akceptuje język <math>\displaystyle L_2</math> przez pusty stos.
+Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena. Lemat
-Automat jest niedeterministyczny i język <math>\displaystyle L_2</math> też jest niedeterministyczny. Nie wiadomo od której litery czytanego
+Ogdena można próbować stosować w tych przypadkach, w których
-słowa  automat powinien wymazywać stos.  Dlatego równolegle z wpisywaniem na stos automat zaczyna wymazywać
+lemat o pompowaniu nie działa.
-za każdym razem gdy
-wystąpią dwie takie same litery obok siebie. Porównaj otrzymany automat z automatami otrzymanymi dla języków <math>\displaystyle L_5</math> i <math>\displaystyle L_6</math>
-z ćwiczenia [[##1|Uzupelnic 1|]].<br>
-ROZWIĄZANIE   punktu 3. Szukany automat  określony  jest rysunkiem <br>
-rys 3    ja-lekcja11-c-rys3  <br>
+{{cwiczenie|2||
+Stosując lemat Ogdena pokaż, że język <math>L=\{a^ib^jc^k: i \not = j, j
+\not = k, k \not = i\}</math> nie jest bezkontekstowy.
+}}
-gdzie <math>\displaystyle A_S = \{z_0,a\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu. Automat ten akceptuje język <math>\displaystyle L_3</math>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-przez stany końcowe i jest automatem deterministycznym.
+Nie wprost, załóżmy, że <math>L</math> jest bezkontekstowy i niech
+<math>M</math> będzie stałą z lematu Ogdena. Rozważmy słowo
+<math>w=a^Mb^{M!+M}c^{2M!+M}</math>. Wyróżnijmy wszystkie pozycje, na których
+znajdują się litery <math>a</math>.
-ROZWIĄZANIE   punktu 4. Szukany automat  określony  jest rysunkiem <br>
+Weźmy rozkład <math>w=u_1w_1uw_2u_2</math>. Zauważmy, że jeśli w <math>w_1</math> lub <math>w_2</math> występują co najmniej dwie różne litery, to <math>w \not \in L</math> (np. jeśli <math>w_1</math> składa się z liter <math>a</math> i <math>b</math> to w słowie <math>w_1^2</math> przynajmniej jedna litera <math>a</math> znajdzie się za jakąś literą <math>b</math>). Ponieważ zaznaczyliśmy pozycje liter <math>a</math>, to z założenia lematu musi
+być <math>w_1 \in a^+</math> lub <math>w_2 \in a^+</math>.
-rys 4   ja-lekcja11-c-rys4  <br>
+Jeśli <math>w_2 \in b^*</math> lub <math>w_2 \in a^*</math> to <math>w_1 \in a^+</math>. Jeśli natomiast <math>w_2 \in a^+</math>, to <math>w_1 \in a^*</math> (dlaczego?).
+Rozważmy przypadek, gdy <math>w_1 \in a^+</math> oraz <math>w_2 \in b^*</math> (pozostałe przypadki
+traktowane są analogicznie). Niech <math>p=|w_1|</math>. Ponieważ <math>1 \leqslant p
+\leqslant M</math>, to <math>p</math> dzieli <math>M!</math>. Niech <math>q=\frac{M!}{p}</math>. Słowo <math>z=u_1w_1^{2q+1}uw_2^{2q+1}u_2</math> należy do <math>L</math>, ale <math>w_1^{2q+1}=a^{p(2q+1)}=a^{2pq+p}=a^{2M!+p}</math>. Ponieważ <math>\sharp_a
+u_1uu_2=M-p</math>, to mamy <math>\sharp_a z = 2M!+p+(M-p)=2M!+M</math>, ale jednocześnie <math>\sharp_c z = 2M!+M = \sharp_a z</math>. Otrzymaliśmy sprzeczność.
-gdzie <math>\displaystyle A_S = \{z_0,a,b \}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu. Automat akceptuje język <math>\displaystyle L_4</math>
+W pozostałych przypadkach w analogiczny sposób dochodzimy do takiej sprzeczności. Zatem <math>L</math> nie jest bezkontekstowy.
-przez stany końcowe i jest automatem niedeterministycznym.  Uzasadnij ten fakt. Czy język <math>\displaystyle L_4</math> jest językiem
+</div></div>
-niedeterministycznym?
-{{cwiczenie|||
+{{cwiczenie|3||
-Napisz na podstawie dowodu twierdzenia [[##lekcja11-w twas-bk|Uzupelnic lekcja11-w twas-bk|]]
+Udowodnij, że dla dowolnego języka <math>L</math> nad alfabetem jednoelementowym
-# algorytm konstrukcji automatu ze stosem
+<center><math>L \in \mathcal{L}_3 \Leftrightarrow L \in \mathcal{L}_2</math>.</center>
-rozpoznającego język generowany przez daną gramatykę bezkontekstową w postaci normalnej Greibach,
-# algorytm konstrukcji gramatyki bezkontekstowej generującej język rozpoznawany przez pusty stsos
-przez dany automat ze stsosem.
 }}
-{{cwiczenie|||
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-Wykorzystując algorytmy z poprzedniego zadania określ
+Wystarczy  udowodnić, że każdy język bezkontekstowy jest regularny. Niech
-# automat akceptujący język generowany przez gramatykę <math>\displaystyle G</math> o zbiorze praw <br>
+<math>L \subset \{a\}^*</math> będzie językiem bezkontekstowym. Z lematu o pompowaniu wynika, że
-<math>\displaystyle  P : v_0 \rightarrow av_0 v_1 \;| \; av_1, v_1 \rightarrow b</math>
+<math>\exists N,M \geqslant 1</math> takie, że każde słowo <math>w \in L</math> o długości <math>|w| > N</math> można
-# gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem <br>
+przedstawić w formie <math>w=u_1w_1uw_2u_2</math>, gdzie  <math>w_{1,}w_{2},v_{1},v_{2},u\in A^{*}</math>  oraz
+<math>|w_1uw_2 |\leqslant M</math>, <math>w_1w_2 \neq 1</math>,  <math>u_1w_1^iuw_2^iu_2 \in L</math> dla <math>i=0,1,.</math>.<br>
+Stąd, że <math>L \subset \{a\}^*</math> wynika, że <math>w=a^pa^k</math> dla pewnego <math>k\leqslant M</math> oraz <math>a^p(a^k)^i \in L</math> dla <math>i=0,1,.</math>..<br>
+Przyjmijmy <math>n=M!</math>. Wówczas dla każdego słowa <math>w \in L</math> o długości <math>|w| > N</math> mamy
+<math>w(a^n)^*=w(a^k)^{\frac{n}{k}}\subset L \subset \{a\}^*</math>. <br>
+Dla <math>i=1,\ldots,n</math> oznaczmy przez
+<center><math>L_i = a^{p+i}(a^n)^* \cap L</math>.</center>
-rys5  ja-lekcja11-c-rys5  <br>
+Jeśli <math>L_i \neq \emptyset</math>, to niech <math>w_i \in L_i</math> będzie słowem o najmniejszej długości. Wówczas
+<center><math>\forall w \in L:|w|>N \;\;w \in \bigcup_{i=1}^n w_i(a^n)^*</math>.</center>
-gdzie <math>\displaystyle A_S = \{z_0,a\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu.
+Zatem <center><math>L=\{w \in L : |w|\leqslant p\} \cup \bigcup_{i=1}^n w_i(a^n)^*</math></center>
+</div></div>
+{{cwiczenie|4||
+Udowodnij, że język    <math>L=\{ a^{n}b^{n}:n \text{ nie jest wielokrotnością liczby } 5 \}</math>
+jest bezkontekstowy.
 }}
-ROZWIĄZANIE. Zarówno w punkcie 1 jak i 2 rozważanym językiem jest  <math>\displaystyle L=\{a^{n}b^n:\:  1\leq n\}  </math> .<br>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-Punkt 1.
+Język <math>L=L_1 \cap \overline{L}_2</math>, gdzie<br>
-Gramatyka jest w postaci Greibach i możemy od razu określić automat.
+<math>L_1=\{ a^{n}b^{n}:n\geqslant 0\}</math>     jest językiem bezkontekstowym,<br>
-Zgodnie z konstrukcją jest to automat jednostanowy zadany rysunkiem <br>
+<math>L_2=\left\{ w \in \{a,b\}^* : |w|=5k \text{ dla pewnego } k\geqslant 0 \right\}</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 regularnym jest
+językiem bezkontekstowym.
+</div></div>
-rys6   ja-lekcja11-c-rys6  <br>
+{{cwiczenie|5||
+Czy gramatyka poprawnych nawiasów  <center><math>(\{v_0\},\{(,)\},v_0, P )</math> gdzie <math>P: v_0 \rightarrow v_0 v_0\;|\;(v_0)\;|\;1</math></center>
-gdzie <math>\displaystyle A_S = \{v_0,v_1,a,b\}</math>, a <math>\displaystyle v_0</math> jest symbolem początkowym stosu. <br>
+jest jednoznaczna?
-Dla przykładu prześledźmy akceptację przez ten automat słowa <math>\displaystyle a^2b^2</math>.<br>
+}}
-<math>\displaystyle (v_0,q) |\!\!\!\Longrightarrow (v_1v_0a,q) |\!\!\!\Longrightarrow^a  (v_1v_0,q) |\!\!\!\Longrightarrow (v_1v_1a,q)
-|\!\!\!\Longrightarrow^a (v_1v_1,q) |\!\!\!\Longrightarrow (v_1b,q) |\!\!\!\Longrightarrow^b (v_1,q)
-|\!\!\!\Longrightarrow^b (b,q)|\!\!\!\Longrightarrow^b (1,q)</math><br>
-Punkt 2.<br>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-Gramatykę zdefiniujemy przez podanie zbioru praw wskazując równocześnie z jakiego przejścia w automacie
+Gramatyka nie jest jednoznaczna. Oto dwie pochodne lewostronne słowa <math>(())()</math>:<br>
-dane prawo powstało.<br>
+<math>v_0\mapsto v_0v_0 \mapsto (v_0)v_0 \mapsto ((v_0))v_0\mapsto (())v_0 \mapsto (())(v_0) \mapsto
-<math>\displaystyle v_0\rightarrow (q_0,z_0,q_1)</math><br>
+(())()</math><br>
-<math>\displaystyle (q_0,z_0,q_1) \rightarrow a (q_0,a,q_1) \longleftrightarrow (z_0,q_0,a)|\!\!\!\Longrightarrow(a,q_0)</math><br>
+<math>v_0\mapsto v_0v_0 \mapsto v_0v_0 v_0 \mapsto (v_0)v_0v_0 \mapsto ((v_0))v_0v_0
-<math>\displaystyle (q_0,a,q_1)\rightarrow a (q_0,a,q_1)(q_1,a,q_1) \longleftrightarrow (a,q_0,a) |\!\!\!\Longrightarrow  (a^2,q_0)</math><br>
+\mapsto (())v_0v_0  \mapsto (())(v_0) v_0 \mapsto
-<math>\displaystyle (q_0,a,q_1)\rightarrow b\longleftrightarrow  (a,q_0,b)  |\!\!\!\Longrightarrow (1,q_1) </math><br>
+(())()v_0 \mapsto (())()</math>
-<math>\displaystyle (q_1,a,q_1) \rightarrow b \longleftrightarrow   (a,q_1,b) |\!\!\!\Longrightarrow (1,q_1)</math><br>
+</div></div>
-Zauważmy, że w obu konstrukcjach otrzymujemy  gramatykę i automat różne od wyjściowych.
+{{cwiczenie|6||
+Określ gramatyki generujące języki:
+# <math>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>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>.
-{{cwiczenie|||
+Czy gramatyki te są jednoznaczne?
-Udowodnij, że każdy automat ze stosem, w którym wielkość stosu jest ograniczona pewną stałą,
-jest równoważny pewnemu automatowi skończenie stanowemu. <br>
 }}
-ROZWIĄZANIE. Dla dowodu tej równoważności wystarczy dla automatu ze
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-stosem z ograniczoną wielkością stosu określić
+Język <math>L_1</math> jest  generowany przez  gramatykę <math>G_1</math>  o zbiorze praw<br>
-równoważny  automat skończenie stanowy. Niech <math>\displaystyle k\geq 1</math> będzie dowolną stałą, a <math>\displaystyle \mathcal{A}_S=(S,A,A_S,f_S,s_0,z_0,S_F)</math>
+<math>
-automatem, w którym wielkość stosu ograniczona jest przez stałą <math>\displaystyle k</math>. Równoważny automat skończenie stanowy jest automatem
+\begin{align}
-niedeterministycznym z pustymi przejściami.<br>
+& 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 ,\\
-Niech <math>\displaystyle \mathcal{A}=(S\times T,A,f,(s_0,z_0),F)</math>, gdzie <math>\displaystyle T=\{w \in A_s^*: |w|\leq k\}</math>, <math>\displaystyle F=S_F\times T</math>,<br>
+& w_1 \rightarrow aw_1 \; |\; bw_2 c \; |\;1,\;\; w_2 \rightarrow  bw_2 c \; |\;1.
-<math>\displaystyle \forall s,s' \in S, \forall z \in A_S, \forall u,v \in A^*_S, \forall a \in A \cup \{1\} </math>
+\end{align}
-<center><math>\displaystyle f((s,uz),a)=\{(s',uv): (uz,s) |\!\!\!\Longrightarrow^a (uv,s')\} </math></center>
+</math><br>
+Gramatyka ta nie jest jednoznaczna. Każde słowo w postaci <math>a^nb^nc^n</math> ma dwa różne wyprowadzenia.
+Na przykład dla słowa <math>abc</math> mamy:
+<center><math>v_0 \mapsto v_1c \mapsto av_2bc \mapsto abc</math></center>
-Co zmieni się w definiowanym automacie skończenie stanowym, jeśli automat ze stosem będzie akceptował przez pusty stos?
+<center><math>v_0 \mapsto aw_1 \mapsto abw_2c \mapsto abc</math></center>
-{{cwiczenie|||
+Język <math>L_2</math> jest  generowany przez  gramatykę <math>G_2</math>  o zbiorze praw<br>
-Oto nieformalny opis automatu z kolejką:
+<math>
+\begin{align}
+& 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.
+\end{align}
+</math><br>
+Gramatyka <math>G_2</math> też nie jest jednoznaczna. Każde słowo w postaci <math>a^n b^n a^p b^p</math> ma dwa różne wyprowadzenia.
+Natomiast język <math>L_2</math> jest również generowany przez gramatykę  <math>G_3</math>
+o zbiorze praw<br>
+<math>
+\begin{align}
+& 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        \;\;
+\end{align}
+</math><br>
+i ta gramatyka jest jednoznaczna, co oznacza, że język <math>L_2</math> jest jednoznaczny.<br>
+Uwaga. Język <math>L_2</math> można rozłożyć na sumę trzech rozłącznych  i bezkontekstowych języków.<br>
+<math>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>G_3</math> generuje niezależnie od siebie te trzy zbiory. Rozkładając analogicznie język <math>L_1</math>, otrzymujemy:<br>
+<math>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>
+Tym razem nie jest to rozkład na sumę języków bezkontekstowych.
+</div></div>
-Automat z kolejką jest podobny do automatu ze stosem, ale zamiast
+{{cwiczenie|7||
-stosu (LIFO - last in, first out) posiada kolejkę FIFO (first in,
+Dana niech będzie gramatyka (<math>v_0</math> jest symbolem początkowym):
-first out). W każdym kroku automat czyta symbol z taśmy (być może
-słowo puste), usuwa z kolejki początkowy symbol (być może słowo
+<center><math>\begin{align} v_0 & \rightarrow & v_0v_1\ |\ v_3v_1 \\
-puste) oraz wstawia na koniec kolejki słowo (być może słowo puste).
+v_1 & \rightarrow & v_1v_2\ |\ v_2v_3 \\
-Automat z kolejką akceptuje słowo przy stanie końcowym lub przy
+v_2 & \rightarrow & v_4v_1\ |\ v_3v_3\ |\ a \\
-pustej kolejce.
+v_3 & \rightarrow & v_1v_2\ |\ v_4v_2\ |\ b \\
-# Podaj formalną definicję automatu z kolejką
+v_4 & \rightarrow & v_3v_4\ |\ v_0v_1\ |\ c
-# Zdefiniuj dwa sposoby akceptacji słowa przez automat: przez stan końcowy oraz przez pustą kolejkę
+\end{align}</math></center>
+Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe
+słowa należą do języka generowanego przez tę gramatykę:
+# <math>w_1=bac</math>,
+# <math>w_2=babcab</math>,
+# <math>w_3=bcaaca</math>.
 }}
-ROZWIĄZANIE punktu 1. Automatem z kolejką nad alfabetem  <math>\displaystyle A
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span><div class="mw-collapsible-content" style="display:none">
-</math>  nazywamy system  <math>\displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F})  </math> , w którym<br>
+<math>w_1 \not \in L(G)</math>, <math>w_2, w_3 \in L(G)</math>.
-<math>\displaystyle A  </math>  - jest alfabetem,  <math>\displaystyle A_{K}  </math>  - jest dowolnym
+</div></div>
-skończonym i niepustym zbiorem zwanym alfabetem kolejki
-(niekoniecznie rozłącznym z  <math>\displaystyle A  </math> ),  <math>\displaystyle Q  </math>  - jest dowolnym,
+<center>ZADANIA DOMOWE</center>
-skończonym i niepustym zbiorem zwanym zbiorem stanów,  <math>\displaystyle f:A_{K}\times Q\times (A\cup \left\{ 1\right\} )\longrightarrow
-\mathcal{P}_{sk}(A_{K}^{*}\times Q)  </math>  jest funkcją przejść, której
+{{cwiczenie|8||
-wartościami są skończone podzbiory  <math>\displaystyle A_{K}^{*}\times Q  </math>  (także
+Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:
-zbiór pusty),  <math>\displaystyle q_{0}\in Q  </math>  jest stanem początkowym,  <math>\displaystyle z_{0}\in
+#  <math>L=\left\{ a^{n}b^{m}c^{k}:k=min\{m,n\}\right\}</math>
-A_{K}  </math>  symbolem początkowym kolejki,  <math>\displaystyle Q_{F}\subset Q  </math>  zbiorem
+#  <math>L=\left\{ a^{n}b^{m}c^{k}:k=mn\right\}</math>
-stanów końcowych.
+#  <math>L=\left\{ a^{n}b^{n^{2}}\right\}</math>
-ROZWIĄZANIE punktu 2.
+}}
-Automat z kolejką <math>\displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F})</math>
+{{cwiczenie|9||
-akceptuje przez stan końcowy słowo <math>\displaystyle w=w_1w_2...w_m \in A^*</math> (<math>\displaystyle w_1,
+Stosując lemat Ogdena, pokaż, że język <math>L=\{a^ib^jc^k: i,j,k>1,\ k
-w_2, ..., w_m \in A, m \geq 0</math>), jeśli istnieje sekwencja stanów
+\not = ir,\ k \not = js</math> gdzie <math>r,s \in \{2,3,...\}\}</math> nie jest
-<math>\displaystyle r_0, r_1, ..., r_m</math> oraz słów <math>\displaystyle s_0, s_1,
+bezkontekstowy.
-..., s_m \in A_{K}^*</math> takich, że:
+}}
-* <math>\displaystyle r_0 = q_0</math>,
-* <math>\displaystyle s_0 = z_0</math>,
-* <math>\displaystyle (r_{i+1},b) \in f(r_i, w_{i+1}, a)</math>, gdzie <math>\displaystyle s_i=au</math> oraz <math>\displaystyle s_{i+1} = ub</math> dla pewnego <math>\displaystyle u \in A_{K}^*</math>,
-* <math>\displaystyle r_m \in Q_{F}</math>.
-Automat akceptuje słowo <math>\displaystyle w</math> przez pustą kolejkę przy takich samych
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span><div class="mw-collapsible-content" style="display:none">
-warunkach jak powyżej, z tym że ostatni z nich ma postać <math>\displaystyle s_m = 1</math>.
+Rozważ słowo <math>a^Pb^Pc^{(P-1)!}</math>, gdzie <math>P</math> jest liczbą
+pierwszą większą niż <math>M+1</math> i większą niż 3, gdzie <math>M</math> jest stałą z
+lematu. Jako pozycje oznaczone wybierz wszystkie pozycje liter <math>c</math>.
+</div></div>
-{{cwiczenie|||
+{{cwiczenie|10||
-Czy moc obliczeniowa automatu z kolejką jest taka sama jak moc
+Udowodnij, że język    <math>L=\left\{ w\overleftarrow{w } : w \in \{a,b\}^* \setminus \{ab^2a\} \right\}</math>
-automatu ze stosem?
+jest bezkontekstowy.
 }}
-WSKAZÓWKA. "Naturalnym" przykładem języka akceptowanego przez
+{{cwiczenie|11||}}
-automat ze stosem był język <math>\displaystyle L=\{w\overleftarrow{w}, w \in A^*\}</math>, gdyż stos
+Czy gramatyka poprawnych nawiasów
-działa w ten sposób, że elementy zdejmowane są z niego w odwrotnej
+<center><math>(\{v_0,v_1\},\{(,)\},v_0, P )</math> gdzie <math>
-kolejności niż były wkładane. Znajdź analogiczny "naturalny"
+P: v_0 \rightarrow v_1 v_0\;|\;1, \;\; v_1 \rightarrow (v_0)</math></center>
-przykład języka akceptowanego przez automat z kolejką. Zwróć uwagę,
-że w kolejce elementy wyjmowane są w takiej samej kolejności, w
-jakiej były do niej wkładane.
-ROZWIĄZANIE. Nie. Automat z kolejką akceptuje język <math>\displaystyle L=\{ww, w \in
+rozważana w przykładzie [http://osilek.mimuw.edu.pl/index.php?title=J%C4%99zyki%2C_automaty_i_obliczenia/Wyk%C5%82ad_9:_J%C4%99zyki_bezkontekstowe_i_ich_gramatyki#przykl.1.2 1.2] jest jednoznaczna?
-A^*\}</math>, który nie jest akceptowany przez automat ze stosem.
-ZADANIA DOMOWE
+{{cwiczenie|12||
+Określ gramatyki generujące języki:
+# <math>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>L_4 =\{a^n b^{2n} : n \geqslant 1 \}\cup \{a^n b^{3n} : n \geqslant 1 \}</math>.
-{{cwiczenie|||
+Czy gramatyki te są jednoznaczne? Wykaż, że język <math>L_4</math> jest jednoznaczny.
+}}
-Określ automaty ze stosem akceptujące następujące  języki przez pusty stos i przez stany końcowe.
+{{cwiczenie|13||
-Wskaż, które języki są deterministyczne.
+Napisz algorytmy rozstrzygające, czy dany język bezkontekstowy jest:
-#  <math>\displaystyle L_5=\left\{ wc\overleftarrow{w} \in \{a,b,c\}^*: w \in \{ a,b\}^*  \right\}   </math>
+# nieskończny,
-#  <math>\displaystyle L_6=\left\{ wx\overleftarrow{w} \in \{a,b\}^*: x \in\{ a,b\}, w \in \{ a,b\}^*  \right\}   </math>
+# niepusty.
-#  <math>\displaystyle L_7=\{a^{n}b^m \in \{a,b\}^*:\:  1\leq m\leq n\}  </math>
-#  <math>\displaystyle L_8=\{a^{n}b^{m} \in \{a,b\}^*:\: m \neq n\}  </math>
 }}
-{{cwiczenie|||
+{{cwiczenie|14||
-Określ automat ze stosem, który rozpoznaje język Łukasiewicza zapisany w wersji postfiksowej ([[##lekcja11-w luk|Uzupelnic lekcja11-w luk|]])
+Dana niech będzie gramatyka (<math>v_0</math> jest symbolem początkowym):
+<center><math>\begin{align} 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.
+\end{align}</math></center>
+Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe
+słowa należą do języka generowanego przez tę gramatykę:
+# <math>w_1=cabba</math>,
+# <math>w_2=baccab</math>,
+# <math>w_3=aabbcc</math>.
 }}