Test GR: Różnice pomiędzy wersjami

Wersja z 11:09, 21 wrz 2006

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYKŁAD}[section] {cw}{PYTANIE}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section]

{prf}{DOWÓD} {sol}{ROZWIĄZANIE} {hint}{WSKAZÓWKA}

{Języki i gramatyki bezkontekstowe - Test}

{Test wielokrotnego wyboru}

Ćwiczenie Języki bezkontekstowe nie będące regularnymi

Wskaż języki bezkontekstowe, które nie są regularne:

a.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}}

b.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_2=\{a^kb^k: k \in \mathds{N}\}}

c.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_3=\{a^kcb^l: k, l \in \mathds{N}\}}

d.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_4=\{a^kcb^k: k \in \mathds{N}\}}

e.: $L_{5} = {w \in {a, b}^{*} : w = \overset{\leftarrow}{w}}$

Rozwiązanie

Ćwiczenie Języki Dycka i Łukasiewicza

Wskaż zdania prawdziwe:

a.: Istnieje gramatyka reularna generująca język Dycka.

b.: Język Dycka jest bezkontekstowy i nie jest regularny.

c.: Istnieje automat skończenie stanowy rozpoznający język

Łukasiewicza.

d.: Język Łukasiewicza da się opisać wyrażeniem regularnym.

e.: Istnieje gramatyka bezkontekstowa bez symboli

bezużytecznych generująca język Dycka.

Rozwiązanie

Ćwiczenie Lemat o pompowaniu

Wskaż języki, które nie są bezkontekstowe:

a.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}}

b.: $L_{2} = {a^{k} b^{n} c^{m} : k < n < m}$

c.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_3=\{a^nb^n: n \in \mathds{N}\}}

d.: Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle L_4=\{ca^nb^n: n \in \mathds{N}\}}

e.: $L_{5} = {w \overset{\leftarrow}{w} a^{| w |} : w \in {a, b}^{*}}$

Rozwiązanie

Ćwiczenie Przynależnośc słowa do języka bezkontekstowego

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}

Wskaż, które z poniższych słów należą do języka generowanego tą gramatyką:

a.: $c a b^{2} a b a b$

b.: $1$

c.: $b^{7}$

d.: $b c a$

e.: $b c a b b$

Rozwiązanie

Ćwiczenie Gramatyki niejednoznaczne

Wskaż gramatyki $G = (V, A, v_{0}, P)$ niejednoznaczne:

a.: $V = {v_{0}, v_{1}, v_{2}, v_{3}}$ , $A = {a, b}$ , $P = {v_{0} \to v_{2} v_{1} | v_{3}$ , $v_{1} \to a v_{1} | a$ , $v_{2} \to v_{2} b | b$ , $v_{3} \to b v_{3} a | b a}$

b.: $V = {v_{0}, v_{1}, v_{2}, v_{3}}$ , $A = {a, b}$ , $P = {v_{0} \to v_{3} v_{1}$ , $v_{1} \to a v_{1} b | b$ , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_2 \rightarrow bv_2a\ |\ b} , $v_{3} \to b v_{2} c}$

c.: $V = {v_{0}, v_{1}}, A = {a, b}$ , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle P=\{v_0 \rightarrow v_0v_1\ |\ b} , $v_{1} \to a v_{1} b | b}$

d.: $V = {v_{0}, . . ., v_{5}}$ , $A = {a}$ , $P = {v_{0} \to a v_{1} | a v_{3}$ , $v_{1} \to a v_{2}$ , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_2 \rightarrow av_1\ |\ 1} , $v_{3} \to a v_{4}$ , $v_{4} \to a v_{5}$ , $v_{5} \to a v_{3} | 1}$

e.: $V = {v_{0}, v_{1}, v_{2}, v_{3}}$ , $A = {a, b}$ , $P = {v_{0} \to v_{2} v_{1}$ , $v_{1} \to a v_{1} | a$ , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_2 \rightarrow v_2b\ |\ b\ |\ v_3} , $v_{3} \to b v_{3} a | b a | b}$

Rozwiązanie

Ćwiczenie Gramatyka bezkontekstowa

Gramatyka $G = (V_{N}, V_{T}, v_{0}, P)$ , gdzie $V_{N} = {v_{0}, . . ., v_{5}}$ , $V_{T} = {a, b}$ , $P = {v_{0} \to a v_{1} | a v_{3}$ , $v_{1} \to a v_{2}$ , $v_{2} \to a v_{1} | 1$ , $v_{3} \to a v_{4}$ , $v_{4} \to a v_{5}$ , $v_{5} \to a v_{3} | 1}$ :

a.: generuje język $(a a)^{+} (a a a)^{+}$

b.: generuje język $(a a + a a a)^{*}$

c.: jest równoważna gramatyce $G^{'} = ({V_{N}}^{'}, V_{T}, v_{0}, P^{'})$ , gdzie

 ${V_{N}}^{'} = {v_{0}, . . ., v_{6}}$ ,  $P^{'} = {v_{0} \to a v_{1}$ ,  $v_{1} \to a v_{2}$ ,  $v_{2} \to a v_{3} | 1$ ,  $v_{3} \to a v_{4} | 1$ ,  $v_{4} \to a v_{5} | 1$ ,  $v_{5} \to a v_{6}$ ,

$v_{6} \to a v_{1} | 1$

d.: jest jednoznaczna

e.: generuje język $L (𝒜)$ , gdzie $𝒜 = (S, A, s_{0}, f, F)$ jest automatem skończenie stanowym takim, że $S = {s_{0}, . . ., s_{4}}$ , $A = {a}$ , $F = {s_{2}, s_{3}, s_{4}}$ ,

$f (s_{0}, a) = f (s_{4}, a) = s_{1}$ , $f (s_{1}, a) = s_{2}$ , $f (s_{2}, a) = s_{3}$ , $f (s_{3}, a) = s_{4}$ .

Rozwiązanie

Ćwiczenie Jednoznaczność języków

Wskaż zdania prawdziwe:

a.: każda gramatyka regularna jest jednoznaczna

b.: każdy język jednoznaczny jest deterministyczny

c.: każdy język regularny jest jednoznaczny

d.: każdy język deterministyczny jest jednoznaczny

e.: język jest jednoznaczny wtw gdy jest deterministyczny

Rozwiązanie

Ćwiczenie Postać normalna Greibach i Chomsky'ego

Wskaż zdania prawdziwe:

a.: Każda gramatyka w postaci normalnej Chomsky'ego jest

bezkontekstowa.

b.: Jeśli gramatyka bezkontekstowa $G$ ma $n$ produkcji, to

równoważna jej gramatyka $G^{'}$ w postaci normalnej Greibach ma co najwyżej $2 n$ produkcji.

c.: Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej

Greibach.

d.: Żadna gramatyka w postaci normalnej Greibach nie jest

regularna.

e.: Każda gramatyka w postaci normalnej Chomsky'ego jest

właściwa.

Rozwiązanie

Ćwiczenie Automat ze stosem

Wskaż zdania prawdziwe:

a.: Każdy automat ze stosem akceptujący przez pusty stos

posiada równoważny automat ze stosem akceptujący przez stany końcowe.

b.: Każdy język bezkontekstowy jest akceptowany przez pusty

stos przez jednostanowy automat ze stosem.

c.: Każdy automat ze stosem, w którym wielkość stosu jest

ograniczona przez pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu.

d.: Każdy automat ze stosem posiada równoważny

deterministyczny automat ze stosem.

e.: Każdy automat ze stosem akceptujący przez stany końcowe

posiada równoważny automat ze stosem akceptujący przez pusty stos.

Rozwiązanie

Ćwiczenie Zamkniętość rodziny języków bezkontekstowych

Rodzina języków bezkontekstowych jest zamknięta ze względu na:

a.: homomorfizm

b.: iloczyn mnogościowy

c.: uzupełnienie

d.: gwiazdkę Kleene'ego

e.: katenację

Rozwiązanie

Ćwiczenie Języki generowane gramatykami bezkontekstowymi

Dane są dwie gramatyki: dla

i = 1, 2 G_{i} = ({v_{0}, v_{1}, v_{2}}, {a, b, c}, v_{0}, P_{i})

, gdzie

P_{1} = {v_{0} \to v_{1} v_{2}, v_{1} \to a v_{1} b, v_{1} \to 1, v_{2} \to c v_{2}, v_{2} \to 1},

P_{2} = {v_{0} \to v_{1} v_{2}, v_{1} \to a v_{1}, v_{1} \to 1, v_{2} \to b v_{2} c, v_{2} \to 1} .

Wówczas:

a.: $L (G_{1}) \cap L (G_{2}) \in̸ ℒ_{2}$

b.: $L (G_{1}) \cap L (G_{2})$ jest językiem skończonym

c.: $L (G_{1}) = L (G_{2})$

d.: $L (G_{1}) \subset L (G_{2})$

e.: $L (G_{1}) \cup L (G_{2}) \in ℒ_{2}$

Rozwiązanie

Ćwiczenie Problemy rozstrzygalne dla języków bezkontekstowych

Niech $L$ będzie językiem bezkontekstowym. Wskaż problemy rozstrzygalne:

a.: $w \in L$

b.: $L = \emptyset$

c.: nieskończoność $L$

d.: równoważność dwóch gramatyk bezkontekstowych

e.: jednoznaczność gramatyki bezkontekstowej

Rozwiązanie

Ćwiczenie Klasy języków

Niech $L \in ℒ_{2}$ , $R \in ℒ_{3}$ . Wówczas:

a.: $L \cap R \in ℒ_{2}$

b.: $L ∖ R \in ℒ_{2}$

c.: $\overline{L} \in ℒ_{2}$

d.: $L \cap \overline{R} \in ℒ_{2}$

e.: $\overline{L} \cap R \in ℒ_{2}$

Rozwiązanie

Ćwiczenie Języki deterministyczne

Wskaż języki deterministyczne:

a.: ${a^{n} b^{n} : n \geq 1} \cup {a^{n} b^{3 n} : n \geq 1}$

b.: ${a^{2 n} : n \geq 1} \cup {a^{3 n} : n \geq 1}$

c.: ${a^{n} b^{n + m} c^{m} : m, n \geq 1}$

d.: ${w x \overset{\leftarrow}{w} : w \in {a, b}^{*}, x \in {a, b}}$

e.: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\ n,m,p \geq 1\}}

Rozwiązanie

Ćwiczenie Języki niejednoznaczne

Wskaż języki niejednoznaczne:

a.: ${a^{n} b^{n} c^{m} d^{m} : n, m \geq 1} \cup {a^{n} b^{m} c^{m} d^{n} : n, m \geq 1}$

b.: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \{a^nb^mc^nd^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^m:\ n,m,p \geq 1\}}

c.: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\ n,m,p \geq 1\}}

d.: ${a^{n} b^{m} c^{m} : n, m \geq 1} \cup {a^{n} b^{n} c^{m} : n, m \geq 1}$

e.: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \{a^nb^mc^md^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^n:\ n,m,p \geq 1\}}

Rozwiązanie

Ćwiczenie Automat ze stosem -- rozpoznawanie języka

Automat ze stosem $𝒜_{S} = (A_{S}, Q, {a, b, c}, z_{0}, q_{0}, P, Q_{F})$ , gdzie $A_{S} = {z_{0}, z, a, c}$ , $Q = {q_{0}, q_{1}, q_{2}, q_{3}}$ , $Q_{F} = {q_{2}}$ , $P = {z_{0} q_{0} a \to z_{0} z q_{0}$ , $z q_{0} a \to z a q_{0}$ , $a q_{0} a \to a^{2} q_{0}$ , $a q_{0} b \to a^{2} q_{1}$ , $z q_{0} b \to z a q_{1}$ , $a q_{1} b \to a^{2} q_{1}$ , $a q_{1} c \to 1 q_{2}$ , $a q_{2} c \to 1 q_{2}$ , $z q_{2} c \to c q_{3}$ , $c q_{2} c \to c q_{2}$ , $c q_{3} c \to c q_{2}}$ :

a.: rozpoznaje język ${a^{n} b^{m} c^{k} : k, n, m > 0, k = n + m}$

b.: rozpoznaje język ${a^{n} b^{m} c^{k} : k, n, m > 0, k > n + m}$

c.: rozpoznaje język ${a^{n} b^{m} c^{k} : k, n, m > 0, k < n + m}$

d.: jest automatem deterministycznym

e.: rozpoznaje język ${a^{n} b^{m} c^{k} : k, n, m > 0, k = n + m}$

Rozwiązanie

Ćwiczenie Problemy nierozstrzygalne w klasie $ℒ_{2}$

Niech $L, L_{1}, L_{2} \in ℒ_{2}$ . Wskaż problemy nierozstrzygalne w klasie $ℒ_{2}$ :

a.: $w \in L$

b.: jednoznaczność $L$

c.: $L_{1} = L_{2}$

d.: $L = \emptyset$

e.: nieskończoność $L$

Rozwiązanie

Ćwiczenie Automat ze stosem -- rozpoznawanie języka

Automat ze stosem $𝒜_{S} = (A_{S}, Q, {a, b}, z_{0}, q_{0}, P, Q_{F})$ , gdzie $A_{S} = {z_{0}, a, b}$ , $Q = {q_{0}, q_{1}}$ , $Q_{F} = {q_{0}}$ , $P = {z_{0} q_{0} a \to z_{0} a q_{0}$ , $a q_{0} a \to a a q_{0}$ , $a q_{0} b \to 1 q_{0}$ , $z_{0} q_{0} b \to z_{0} b q_{1}$ , $b q_{1} b \to b b q_{1}$ , $b q_{1} a \to 1 q_{1}$ , $z_{0} q_{1} \to z_{0} q_{0}}$ :

a.: rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w}$

b.: rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w \leq ♯_{b} w}$

c.: rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w \geq ♯_{b} w}$

d.: jest automatem deterministycznym

e.: rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w}$

Rozwiązanie

Ćwiczenie Algorytm CYK

Algorytm Cocke'a-Youngera-Kasamiego:

a.: sprawdza, czy słowo należy do języka bezkontekstowego

b.: działa w czasie $O (n^{2} \log n)$

c.: jest niedeterministyczny

d.: może dostać na wejście dowolną gramatykę bezkontekstową

e.: działa w oparciu o zasadę programowania dynamicznego

Rozwiązanie

8888888888888888888888888888888888888888888888888888888888 Wskaż, które z poniższych struktur są monoidami:

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle (\mathds{Z}_{mod\ 2}, \cdot)} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle (\mathds{N}_1, +)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle \mathds{N}_1=\{1,2,3,...\}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle (\mathds{N}_p,+)} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle \mathds{N}_p} jest zbiorem wszystkich liczb pierwszych Źle

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle (\mathds{R}, \cdot)} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle (\mathds{Z}, +)} Dobrze

Wskaż stwierdzenia prawdziwe:

$a b b a a a \in {a a, b b}^{*}$ Źle

$a b b a a a \in {a, b}^{*}$ Dobrze

$a b b a a a \in {a b b, a}^{*}$ Dobrze

$a b b a a a \in {b a, a b}^{*}$ Źle

$a b b a a a \in {a a, a b, b a}^{*}$ Dobrze

Wskaż, które z poniższych odwzorowań są homomorfizmami:

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: (\mathds{R},+) \rightarrow (\mathds{Z},+)} , $h (x) = 3 x$ Źle

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: (\mathds{R},+) \rightarrow (\mathds{R},+)} , $h (x) = 3 x$ Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)} , $h (x) = 3 x$ Źle

$h : {a, b}^{*} \to {a, b}^{*}$ , $h (a) = a^{2}$ , $h (b) = a b^{2}$ Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+)} , $h (a) = 1$ , $h (b) = 1$ Dobrze

Dany niech będzie system przepisujący $R S = ({a, b, c}, {(a, b), (b, c), (b, a), (c c, b))$ oraz niech $I = {c c b}$ . Wskaż stwierdzenia prawdziwe:

$a b c \in L_{g e n} (R S, I)$ Źle

$c c b \in L_{g e n} (R S, I)$ Dobrze

$b b \in L_{g e n} (R S, I)$ Dobrze

$a a b \in L_{g e n} (R S, I)$ Źle

$a a \in L_{g e n} (R S, I)$ Dobrze

Wyrażenie regularne

((a a + b b)^{*} (a b + b a) (a a + b b)^{*} (a b + b a))^{*} (a a + b b)^{*}

reprezentuje język:

${w \in {a, b}^{*} : ♯_{a} w = 2 k$ , $♯_{b} w = 2 l$ , $k, l > 0}$ Dobrze

${w \in {a, b}^{*} : ♯_{a} w - ♯_{b} w = 0 (m o d 2)}$ Źle

${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w = 2 k, k \geq 0}$ Źle

${w \in {a, b}^{*} : ♯_{a} w - ♯_{b} w = 1 (m o d 2)}$ Źle

${w \in {a, b}^{*} : ♯_{a} w = 4 k$ , $♯_{b} w = 4 l$ , $k, l \geq 0}$ Źle

Niech $A = {a, b}$ oraz $L = a A^{*} a$ . Wskaż zdania prawdziwe:

minimalny automat akceptujący $L$ ma 5 stanów Źle

ilość klas równoważności prawej kongruencji syntaktycznej $P_{L}^{r}$ wyznaczonej przez $L$ jest równa 4 Dobrze

$A^{*} ∖ L = b A^{*} b + b$ Źle

$A^{*} ∖ L = b A^{*} + a A^{*} b + a + 1$ Dobrze

monoid przejśc minimalnego automatu akceptującego $L$ ma 6 elementów Dobrze

Niech $L$ będzie dowolnym językiem regularnym. Wskaż zdania prawdziwe:

$L$ jest rozpoznawany przez pewien niedeterministyczny automat skończenie stanowy z pustymi przejściami Dobrze

$L$ jest rozpoznawany przez automat deterministyczny skończenie stanowy Dobrze

$L$ jest rozpoznawany przez niedeterministyczny automat z pustymi przejściami o jednoelementowym zbiorze stanów początkowych Dobrze

Nie istnieje automat niedeterministyczny z pustymi przejściami rozpoznający $L$ i taki, że zbiór stanów początkowych jest jednoelementowy Źle

Nie istnieje gramatyka lewoliniowa generująca $L$ Źle

Niech $L_{1}$ , $L_{2}$ będą językami rozpoznawanymi odpowiednio przez automaty o $n_{1}$ i $n_{2}$ stanach. Aby stwierdzić, dla dowolnego słowa $w$ , czy jest ono rozpoznawane przez oba automaty, wystarczy skonstruować odpowiedni automat mający

$n_{1} \cdot n_{2}$ stanów Dobrze

$O (n_{1} + n_{2})$ stanów Dobrze

$n_{1}$ stanów Źle

$n_{2}$ stanów Źle

3 stany Źle

Język $L$ składa się ze wszystkich słów nad alfabetem $A = {a, b}$ nie zawierających podsłowa $a^{3}$ . Wskaż wyrażenie regularne reprezentujące $L$ :

$(b^{*} (1 + a + a a) b^{*})^{*}$ Źle

$(b^{*} (1 + a + a a) b b^{*})^{*}$ Źle

$(b + a b + a a b)^{*} + (b + a b + a a b)^{*} a + (b + a b + a a b)^{*} a a$ Dobrze

$((1 + a + a a) b b^{*})^{*} (1 + a + a a)$ Dobrze

$b^{*} (a + a a) b b^{*})^{*} (1 + a + a a)$ Dobrze

Wskaż warunki równoważne temu, by język $L$ był akceptowany przez automat skończenie stanowy:

Istnieje liczba naturalna $N \geq 1$ taka, że każde słowo $w \in L$ o długości $| w | \geq N$ można przedstawić jako katenację $w = v_{1} u v_{2}$ , gdzie $v_{1}, v_{2} \in A^{*}$ , $u \in A^{+}$ oraz $v_{1} u^{*} v_{2} \subset L$ . Źle

Istnieje skończony monoid $M$ i homomorfizm $ϕ : A^{*} \to M$ taki, że $ϕ^{- 1} (ϕ (L)) = L$ . Dobrze

$L$ jest sumą wybranych klas równoważności pewnej

kongruencji

ρ

na

A^{*}

:

L = \cup_{w \in L} [w]_{ρ} .

Źle

$L \in ℛ ℰ 𝒢 (A^{*})$ . Dobrze

$L$ jest akceptowany przez deterministyczny automat skończenie stanowy z jednym stanem końcowym. Źle

Automat $𝒜 = (S, A, s_{0}, f, F)$ , gdzie $S = {s_{0}, s_{1}, s_{2}, s_{3}}$ , $A = {a, b}$ , $F = {s_{1}}$ ,


$f$	$s_{0}$	$s_{1}$	$s_{2}$	$s_{3}$
$a$	$s_{1}$	$s_{0}$	$s_{3}$	$s_{2}$
$b$	$s_{3}$	$s_{2}$	$s_{1}$	$s_{0}$

jest automatem minimalnym Dobrze

rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = 2 k, ♯_{b} w = 2 l + 1$ , $k, l \geq 0}$ Źle

rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = 2 k, ♯_{b} w = 2 l$ , $k, l \geq 0}$ Źle

rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = 2 k + 1, ♯_{b} w = 2 l$ , $k, l \geq 0}$ Dobrze

rozpoznaje język ${w \in {a, b}^{*} : ♯_{a} w = 2 k + 1, ♯_{b} w = 2 l + 1$ , $k, l \geq 0}$ Źle

Które z poniższych równości dla wyrażeń regularnych są prawdziwe?

$r^{*} r^{*} = r^{*}$ Dobrze

$(r + s)^{*} = r^{*} + s^{*}$ Źle

$(r^{*} + s^{*})^{*} = (r^{*} s^{*})^{*}$ Dobrze

$r + r = r$ Dobrze

$(r s)^{*} r = r (s r)^{*}$ Dobrze

Wskaż języki regularne:

${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w (m o d 3)}$ Dobrze

${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w}$ Źle

${w \in {a, b}^{*} : | w | = 2^{n}, n > 0}$ Źle

${w \in {a, b}^{*} : ♯_{a} w \cdot ♯_{b} w = 100}$ Dobrze

${a^{n} : n = 3 k$ lub $n = 5 k, k \geq 0}$ Dobrze

Dany jest automat $𝒜 = (S, A, s_{0}, f, F)$ , gdzie $S = {s_{0}, s_{1}, s_{2}}$ , $A = {a, b}$ , $F = {s_{0}, s_{1}}$ ,


$f$	$s_{0}$	$s_{1}$	$s_{2}$
$a$	$s_{1}$	$s_{0}$	$s_{2}$
$b$	$s_{0}$	$s_{2}$	$s_{2}$

Wskaż zdania prawdziwe:

$L (𝒜) = (a^{2} + b)^{*} (a + 1)$ . Dobrze

Równoważny automat minimalny ma 2 stany. Źle

Jeśli $w \in L (𝒜)$ , to dla każdych $v, u \in A^{*}$ takich, że $w = v b u$ zachodzi $♯_{a} v = 2 k$ dla pewnego $k \geq 0$ . Dobrze

$a^{*} b^{*} \subset L (𝒜)$ . Źle

Jeśli $w \in L (𝒜)$ , to $a^{2} b$ jest podsłowem słowa $w$ . Źle

Dany niech będzie automat niedeterministyczny $𝒜_{N D} = (Q, A, {q_{0}}, f, F)$ , gdzie $Q = {q_{0}, q_{1}, q_{2}}$ , $A = {a, b}$ , $F = {q_{2}}$ ,


$f$	$q_{0}$	$q_{1}$	$q_{2}$
$a$	${q_{1}}$	${q_{0}, q_{2}}$	${q_{2}}$
$b$	$\emptyset$	$\emptyset$	${q_{1}}$

Wskaż zdania prawdziwe:

$L (𝒜_{N D}) = a^{2} (a + b a)^{*}$ . Dobrze

$L (𝒜_{N D}) = a (a a^{*} b)^{*} a a^{*}$ . Dobrze

Równoważny automat deterministyczny posiada 3 stany. Źle

$L (𝒜_{N D}) = a^{2} (a^{*} b)^{*} a a^{*}$ . Źle

Równoważny minimalny automat deterministyczny posiada 4 stany. Dobrze

Twierdzenie orzekające o równości zachodzącej pomiędzy rodziną języków regularnych a rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów znane jest jako:

twierdzenie Nerode'a Źle

teza Churcha Źle

lemat Ardena Źle

lemat o pompowaniu Źle

twierdzenie Kleene'ego Dobrze

Wskaż monoid przejść automatu o następującej funkcji przejścia:


$f$	$s_{0}$	$s_{1}$	$s_{2}$	$s_{3}$
$a$	$s_{1}$	$s_{0}$	$s_{3}$	$s_{2}$
$b$	$s_{3}$	$s_{2}$	$s_{1}$	$s_{0}$

$({τ_{𝒜} (1), τ_{𝒜} (a), τ_{𝒜} (b), τ_{𝒜} (a b)}, \circ)$ Dobrze

$({τ_{𝒜} (1), τ_{𝒜} (a)}, \circ)$ Źle

$({τ_{𝒜} (1), τ_{𝒜} (a), τ_{𝒜} (a b)}, \circ)$ Źle

$({τ_{𝒜} (1), τ_{𝒜} (a), τ_{𝒜} (b)}, \circ)$ Źle

$({τ_{𝒜} (a), τ_{𝒜} (b), τ_{𝒜} (a b), τ_{𝒜} (b a)}, \circ)$ Źle

Niech $L_{1}, L_{2}$ będą językami regularnymi. Wskaż problemy rozstrzygalne.

$w \in L_{1}$ Dobrze

$w \in L_{1} \cap L_{2}$ Dobrze

$L_{1} \cap L_{2} = \emptyset$ Dobrze

nieskończoność $L_{1}$ Dobrze

$L_{1} = \emptyset$ Dobrze

Algorytm determinizacji automatu:

jest deterministyczny Dobrze

działa w czasie wielomianowym Źle

może się zapętlić Źle

działa w czasie eksponencjalnym Dobrze

kończy działanie błędem, jeśli na wejściu podany został automat deterministyczny Źle

Wskaż zdania prawdziwe:

istnieje algorytm minimalizacji automatu działający w czasie $n \log n$ Dobrze

żaden algorytm minimalizacji nie może działać szybciej niż w czasie $O (n^{2})$ Źle

algorytm minimalizacji zawsze zwróci automat o mniejszej liczbie stanów niż automat podany na wejściu Źle

algorytmy minimalizacji są algorytmami niedeterministycznymi Źle

algorytmy minimalizacji nie działają dla automatów jednostanowych Źle

Test GR: Różnice pomiędzy wersjami

Wersja z 11:09, 21 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 7: / Linia 7: @@
 ------------------------------
+{theor}{TWIERDZENIE}[section]
+{rem}{UWAGA}[section]
+{corol}{WNIOSEK}[section]
+{fact}{FAKT}[section]
+{ex}{PRZYKŁAD}[section]
+{cw}{PYTANIE}[section]
+{defin}{DEFINICJA}[section]
+{lem}{LEMAT}[section]
+{prf}{DOWÓD}
+{sol}{ROZWIĄZANIE}
+{hint}{WSKAZÓWKA}
+{Języki i gramatyki bezkontekstowe - Test}
+{Test wielokrotnego wyboru}
+{{cwiczenie|Języki bezkontekstowe nie będące regularnymi||
+<br>
+Wskaż języki bezkontekstowe, które nie są regularne:
+; a.
+:  <math>\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}</math>
+; b.
+:  <math>\displaystyle L_2=\{a^kb^k: k \in \mathds{N}\}</math>
+; c.
+:  <math>\displaystyle L_3=\{a^kcb^l: k, l \in \mathds{N}\}</math>
+; d.
+:  <math>\displaystyle L_4=\{a^kcb^k: k \in \mathds{N}\}</math>
+; e.
+:  <math>\displaystyle L_5=\{w \in \{a,b\}^*: w = \overleftarrow{w}\}</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">
+b,d,e
+</div></div>
+{{cwiczenie|Języki Dycka i Łukasiewicza||
+<br>
+Wskaż zdania prawdziwe:
+; a.
+:  Istnieje gramatyka reularna generująca język Dycka.
+; b.
+:  Język Dycka jest bezkontekstowy i nie jest regularny.
+; c.
+:  Istnieje automat skończenie stanowy rozpoznający język
+Łukasiewicza.
+; d.
+:  Język Łukasiewicza da się opisać wyrażeniem regularnym.
+; e.
+:  Istnieje gramatyka bezkontekstowa bez symboli
+bezużytecznych generująca język Dycka.
+}}
+<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">
+b, e
+</div></div>
+{{cwiczenie|Lemat o pompowaniu||
+<br>
+Wskaż języki, które nie są bezkontekstowe:
+; a.
+:  <math>\displaystyle L_1=\{a^kb^l: k, l \in \mathds{N}\}</math>
+; b.
+:  <math>\displaystyle L_2=\{a^kb^nc^m: k < n < m\}</math>
+; c.
+:  <math>\displaystyle L_3=\{a^nb^n: n \in \mathds{N}\}</math>
+; d.
+:  <math>\displaystyle L_4=\{ca^nb^n: n \in \mathds{N}\}</math>
+; e.
+:  <math>\displaystyle L_5=\{w\overleftarrow{w}a^{|w|}: w \in \{a,b\}^*\}</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">
+b
+</div></div>
+{{cwiczenie|Przynależnośc słowa do języka bezkontekstowego||
+<br>
+Dana niech będzie gramatyka (<math>\displaystyle v_0</math> jest symbolem początkowym):
+<center><math>\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</math></center>
+Wskaż, które z poniższych słów należą do języka generowanego tą
+gramatyką:
+; a.
+:  <math>\displaystyle cab^2abab</math>
+; b.
+:  <math>\displaystyle 1</math>
+; c.
+:  <math>\displaystyle b^7</math>
+; d.
+:  <math>\displaystyle bca</math>
+; e.
+:  <math>\displaystyle bcabb</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">
+a, c, e
+</div></div>
+{{cwiczenie|Gramatyki niejednoznaczne||
+<br>
+Wskaż gramatyki <math>\displaystyle G=(V, A, v_0, P)</math> niejednoznaczne:
+; a.
+:  <math>\displaystyle V=\{v_0,v_1,v_2,v_3\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
+v_2v_1\ |\ v_3</math>, <math>\displaystyle v_1 \rightarrow av_1\ |\ a</math>, <math>\displaystyle v_2 \rightarrow
+v_2b\ |\ b</math>, <math>\displaystyle v_3 \rightarrow bv_3a\ |\ ba\}</math>
+; b.
+:  <math>\displaystyle V=\{v_0, v_1, v_2, v_3 \}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
+v_3v_1</math>, <math>\displaystyle v_1 \rightarrow av_1b\ |\ b</math>, <math>\displaystyle v_2 \rightarrow bv_2a\ |\
+b</math>, <math>\displaystyle v_3 \rightarrow bv_2c\}</math>
+; c.
+:  <math>\displaystyle V=\{v_0, v_1\}, A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow v_0v_1\
+|\ b</math>, <math>\displaystyle v_1 \rightarrow av_1b\ |\ b\}</math>
+; d.
+:  <math>\displaystyle V=\{v_0, ..., v_5\}</math>, <math>\displaystyle A=\{a\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
+av_1\ |\ av_3</math>, <math>\displaystyle v_1 \rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_1\ |\
+</math>, <math>\displaystyle v_3 \rightarrow av_4</math>, <math>\displaystyle v_4 \rightarrow av_5</math>, <math>\displaystyle v_5 \rightarrow
+av_3\ |\ 1\}</math>
+; e.
+:  <math>\displaystyle V=\{v_0,v_1,v_2,v_3\}</math>, <math>\displaystyle A=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow
+v_2v_1</math>, <math>\displaystyle v_1 \rightarrow av_1\ |\ a</math>, <math>\displaystyle v_2 \rightarrow v_2b\ |\
+b\ |\ v_3</math>, <math>\displaystyle v_3 \rightarrow bv_3a\ |\ ba\ |\ b \}</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">
+a, d, e
+</div></div>
+{{cwiczenie|Gramatyka bezkontekstowa||
+<br>
+Gramatyka <math>\displaystyle G=(V_N, V_T, v_0, P)</math>, gdzie <math>\displaystyle V_N=\{v_0,..., v_5\}</math>,
+<math>\displaystyle V_T=\{a,b\}</math>, <math>\displaystyle P=\{v_0 \rightarrow av_1\ |\ av_3</math>, <math>\displaystyle v_1
+\rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_1\ |\ 1</math>, <math>\displaystyle v_3 \rightarrow
+av_4</math>, <math>\displaystyle v_4 \rightarrow av_5</math>, <math>\displaystyle v_5 \rightarrow av_3\ |\ 1\}</math>:
+; a.
+:  generuje język <math>\displaystyle (aa)^+(aaa)^+</math>
+; b.
+:  generuje język <math>\displaystyle (aa+aaa)^*</math>
+; c.
+:  jest równoważna gramatyce <math>\displaystyle G'=(V_N', V_T, v_0, P')</math>, gdzie
+ <math>\displaystyle V_N'=\{v_0, ..., v_6\}</math>, <math>\displaystyle P'=\{v_0 \rightarrow av_1</math>, <math>\displaystyle v_1
+\rightarrow av_2</math>, <math>\displaystyle v_2 \rightarrow av_3\ |\ 1</math>, <math>\displaystyle v_3 \rightarrow
+av_4\ |\ 1</math>, <math>\displaystyle v_4 \rightarrow av_5\ |\ 1</math>, <math>\displaystyle v_5 \rightarrow av_6</math>,
+<math>\displaystyle v_6 \rightarrow av_1\ |\ 1</math>
+; d.
+:  jest jednoznaczna
+; e.
+:  generuje język <math>\displaystyle L(\mathcal{A})</math>, gdzie <math>\displaystyle \mathcal{A}=(S, A,
+s_0, f, F)</math> jest automatem skończenie stanowym takim, że <math>\displaystyle S=\{s_0,
+..., s_4\}</math>, <math>\displaystyle A=\{a\}</math>, <math>\displaystyle F=\{s_2, s_3, s_4\}</math>,
+<math>\displaystyle f(s_0,a)=f(s_4,a)=s_1</math>, <math>\displaystyle f(s_1, a)=s_2</math>, <math>\displaystyle f(s_2, a)=s_3</math>, <math>\displaystyle f(s_3,
+a)=s_4</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">
+a, c
+</div></div>
+{{cwiczenie|Jednoznaczność języków||
+<br>
+Wskaż zdania prawdziwe:
+; a.
+:  każda gramatyka regularna jest jednoznaczna
+; b.
+:  każdy język jednoznaczny jest deterministyczny
+; c.
+:  każdy język regularny jest jednoznaczny
+; d.
+:  każdy język deterministyczny jest jednoznaczny
+; e.
+:  język jest jednoznaczny wtw gdy 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">
+c, d
+</div></div>
+{{cwiczenie|Postać normalna Greibach i Chomsky'ego||
+<br>
+Wskaż zdania prawdziwe:
+; a.
+:  Każda gramatyka w postaci normalnej Chomsky'ego jest
+bezkontekstowa.
+; b.
+:  Jeśli gramatyka bezkontekstowa <math>\displaystyle G</math> ma <math>\displaystyle n</math> produkcji, to
+równoważna jej gramatyka <math>\displaystyle G'</math> w postaci normalnej Greibach ma co
+najwyżej <math>\displaystyle 2n</math> produkcji.
+; c.
+:  Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej
+Greibach.
+; d.
+:  Żadna gramatyka w postaci normalnej Greibach nie jest
+regularna.
+; e.
+:  Każda gramatyka w postaci normalnej Chomsky'ego jest
+właściwa.
+}}
+<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">
+a,e
+</div></div>
+{{cwiczenie|Automat ze stosem||
+<br>
+Wskaż zdania prawdziwe:
+; a.
+:  Każdy automat ze stosem akceptujący przez pusty stos
+posiada równoważny automat ze stosem akceptujący przez stany
+końcowe.
+; b.
+:  Każdy język bezkontekstowy jest akceptowany przez pusty
+stos przez jednostanowy automat ze stosem.
+; c.
+:  Każdy automat ze stosem, w którym wielkość stosu jest
+ograniczona przez pewną stałą, jest równoważny pewnemu automatowi
+skończenie stanowemu.
+; d.
+:  Każdy automat ze stosem posiada równoważny
+deterministyczny automat ze stosem.
+; e.
+:  Każdy automat ze stosem akceptujący przez stany końcowe
+posiada równoważny automat ze stosem akceptujący przez pusty stos.
+}}
+<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">
+a,b,c,e
+</div></div>
+{{cwiczenie|Zamkniętość rodziny języków bezkontekstowych||
+<br>
+Rodzina języków bezkontekstowych jest zamknięta ze względu na:
+; a.
+:  homomorfizm
+; b.
+:  iloczyn mnogościowy
+; c.
+:  uzupełnienie
+; d.
+:  gwiazdkę Kleene'ego
+; e.
+:  katenację
+}}
+<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">
+a,d,e
+</div></div>
+{{cwiczenie|Języki generowane gramatykami bezkontekstowymi||
+<br>
+Dane są dwie gramatyki: dla <math>\displaystyle i=1,2\displaystyle G_i=(\{v_0,v_1,v_2\},\{a,b,c\},v_0,P_i)</math>, gdzie <center><math>\displaystyle P_1=\{v_0
+\rightarrow v_1v_2,\ v_1 \rightarrow av_1b,\ v_1 \rightarrow 1,\ v_2
+\rightarrow cv_2,\ v_2 \rightarrow 1\},</math></center>
+ <center><math>\displaystyle P_2 = \{v_0 \rightarrow
+v_1v_2,\ v_1 \rightarrow av_1,\ v_1 \rightarrow 1,\ v_2 \rightarrow
+bv_2c,\ v_2 \rightarrow 1\}.</math></center>
+ Wówczas:
+; a.
+:  <math>\displaystyle L(G_1) \cap L(G_2) \not \in \mathcal{L}_2</math>
+; b.
+:  <math>\displaystyle L(G_1) \cap L(G_2)</math> jest językiem skończonym
+; c.
+:  <math>\displaystyle L(G_1)=L(G_2)</math>
+; d.
+:  <math>\displaystyle L(G_1) \subset L(G_2)</math>
+; e.
+:  <math>\displaystyle L(G_1) \cup L(G_2)\in \mathcal{L}_2</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">
+a,e
+</div></div>
+{{cwiczenie|Problemy rozstrzygalne dla języków bezkontekstowych||
+<br>
+Niech <math>\displaystyle L</math> będzie językiem bezkontekstowym. Wskaż problemy rozstrzygalne:
+; a.
+:  <math>\displaystyle w \in L</math>
+; b.
+:  <math>\displaystyle L = \emptyset</math>
+; c.
+:  nieskończoność <math>\displaystyle L</math>
+; d.
+:  równoważność dwóch gramatyk bezkontekstowych
+; e.
+:  jednoznaczność gramatyki bezkontekstowej
+}}
+<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">
+a,b,c
+</div></div>
+{{cwiczenie|Klasy języków||
+<br>
+Niech <math>\displaystyle L \in \mathcal{L}_2</math>, <math>\displaystyle R \in \mathcal{L}_3</math>. Wówczas:
+; a.
+:  <math>\displaystyle L \cap R \in \mathcal{L}_2</math>
+; b.
+:  <math>\displaystyle L \backslash R \in \mathcal{L}_2</math>
+; c.
+:  <math>\displaystyle \overline{L} \in \mathcal{L}_2</math>
+; d.
+:  <math>\displaystyle L \cap \overline{R} \in \mathcal{L}_2</math>
+; e.
+:  <math>\displaystyle \overline{L} \cap R \in \mathcal{L}_2</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">
+a,b,d
+</div></div>
+{{cwiczenie|Języki deterministyczne||
+<br>
+Wskaż języki deterministyczne:
+; a.
+:  <math>\displaystyle \{a^nb^n:\ n \geq 1\} \cup \{a^nb^{3n}:\ n \geq 1\}</math>
+; b.
+:  <math>\displaystyle \{a^{2n}:\ n \geq 1\} \cup \{a^{3n}:\ n \geq 1\}</math>
+; c.
+:  <math>\displaystyle \{a^nb^{n+m}c^m:\ m,n \geq 1\}</math>
+; d.
+:  <math>\displaystyle \{wx\overleftarrow{w}:\ w \in \{a,b\}^*,\ x \in \{a,b\}
+\}</math>
+; e.
+:  <math>\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\
+n,m,p \geq 1\}</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">
+b,c,e
+</div></div>
+{{cwiczenie|Języki niejednoznaczne||
+<br>
+Wskaż języki niejednoznaczne:
+; a.
+:  <math>\displaystyle \{a^nb^nc^md^m:\ n,m \geq 1\} \cup \{a^nb^mc^md^n:\ n,m
+\geq 1\}</math>
+; b.
+:  <math>\displaystyle \{a^nb^mc^nd^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^m:\
+n,m,p \geq 1\}</math>
+; c.
+:  <math>\displaystyle \{a^nb^na^mb^p:\ n,m,p \geq 1\} \cup \{a^nb^ma^pb^p:\
+n,m,p \geq 1\}</math>
+; d.
+:  <math>\displaystyle \{a^nb^mc^m:\ n,m \geq 1\} \cup \{a^nb^nc^m:\ n,m \geq
+\}</math>
+; e.
+:  <math>\displaystyle \{a^nb^mc^md^p:\ n,m,p \geq 1\} \cup \{a^nb^mc^pd^n:\
+n,m,p \geq 1\}</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">
+a,b,d
+</div></div>
+{{cwiczenie|Automat ze stosem -- rozpoznawanie języka||
+<br>
+Automat ze stosem <math>\displaystyle \mathcal{A}_S = (A_S, Q, \{a,b,c\}, z_0, q_0, P,
+Q_F)</math>, gdzie <math>\displaystyle A_S=\{z_0,z,a,c\}</math>, <math>\displaystyle Q=\{q_0,q_1,q_2,q_3\}</math>,
+<math>\displaystyle Q_F=\{q_2\}</math>, <math>\displaystyle P = \{z_0q_0a \rightarrow z_0zq_0</math>, <math>\displaystyle zq_0a
+\rightarrow zaq_0</math>, <math>\displaystyle aq_0a \rightarrow a^2q_0</math>, <math>\displaystyle aq_0b \rightarrow
+a^2q_1</math>, <math>\displaystyle zq_0b \rightarrow zaq_1</math>, <math>\displaystyle aq_1b \rightarrow a^2q_1</math>,
+<math>\displaystyle aq_1c \rightarrow 1q_2</math>, <math>\displaystyle aq_2c \rightarrow 1q_2</math>, <math>\displaystyle zq_2c
+\rightarrow cq_3</math>, <math>\displaystyle cq_2c \rightarrow cq_2</math>, <math>\displaystyle cq_3c \rightarrow
+cq_2\}</math>:
+; a.
+:  rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k \not = n+m\}</math>
+; b.
+:  rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k > n+m\}</math>
+; c.
+:  rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k < n+m\}</math>
+; d.
+:  jest automatem deterministycznym
+; e.
+:  rozpoznaje język <math>\displaystyle \{a^nb^mc^k:\ k,n,m > 0,\ k = n+m\}</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">
+a,d
+</div></div>
+{{cwiczenie|Problemy nierozstrzygalne w klasie <math>\displaystyle \mathcal{L}_2</math>||
+<br>
+Niech <math>\displaystyle L, L_1, L_2 \in \mathcal{L}_2</math>. Wskaż problemy
+nierozstrzygalne w klasie <math>\displaystyle \mathcal{L}_2</math>:
+; a.
+:  <math>\displaystyle w \in L</math>
+; b.
+:  jednoznaczność <math>\displaystyle L</math>
+; c.
+:  <math>\displaystyle L_1=L_2</math>
+; d.
+:  <math>\displaystyle L = \emptyset</math>
+; e.
+:   nieskończoność <math>\displaystyle L</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">
+b,c
+</div></div>
+{{cwiczenie|Automat ze stosem -- rozpoznawanie języka||
+<br>
+Automat ze stosem <math>\displaystyle \mathcal{A}_S = (A_S, Q, \{a,b\}, z_0, q_0, P,
+Q_F)</math>, gdzie <math>\displaystyle A_S=\{z_0,a,b\}</math>, <math>\displaystyle Q=\{q_0,q_1\}</math>, <math>\displaystyle Q_F=\{q_0\}</math>, <math>\displaystyle P =
+\{z_0q_0a \rightarrow z_0aq_0</math>, <math>\displaystyle aq_0a \rightarrow aaq_0</math>, <math>\displaystyle aq_0b
+\rightarrow 1q_0</math>, <math>\displaystyle z_0q_0b \rightarrow z_0bq_1</math>, <math>\displaystyle bq_1b \rightarrow
+bbq_1</math>, <math>\displaystyle bq_1a \rightarrow 1q_1</math>, <math>\displaystyle z_0q_1 \rightarrow z_0q_0\}</math>:
+; a.
+:  rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \not = \sharp_bw\}</math>
+; b.
+:  rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \leq \sharp_bw\}</math>
+; c.
+:  rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \geq \sharp_bw\}</math>
+; d.
+:  jest automatem deterministycznym
+; e.
+:  rozpoznaje język <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\}</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">
+c,d
+</div></div>
+{{cwiczenie|Algorytm CYK||
+<br>
+Algorytm Cocke'a-Youngera-Kasamiego:
+; a.
+:  sprawdza, czy słowo należy do języka bezkontekstowego
+; b.
+:  działa w czasie <math>\displaystyle O(n^2\log n)</math>
+; c.
+:  jest niedeterministyczny
+; d.
+:  może dostać na wejście dowolną gramatykę bezkontekstową
+; e.
+:  działa w oparciu o zasadę programowania dynamicznego
+}}
+<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">
+a, e
+</div></div>
+8888888888888888888888888888888888888888888888888888888888
 <quiz>
 Wskaż, które z poniższych struktur są monoidami: