Test GR: Różnice pomiędzy wersjami

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 11:30, 21 wrz 2006

Wskaż zdania prawdziwe:

a.: Automat liniowo ograniczony może dopisywać literę na

początku lub na końcu czytanego słowa. Źle

b.: Maszyna Turinga może zmieniać długość czytanego słowa. Dobrze

c.: Automat ze stosem może w jednym przejściu dowolną literę słowa zapisanego na stosie zastąpić dowolnym słowem nad alfabetem stosu. Źle

d.: Automat ze stosem i automat liniowo ograniczony mogą

zmieniać stan bez czytania litery. Dobrze

e.: Automat liniowo ograniczony może w czytanym słowie

zmieniać dowolną literę z alfabetu taśmy Źle

Rozwiązanie

Wskaż zdania prawdziwe:

a.: Każda gramatyka bezkontekstowa jest kontekstowa. Źle

b.: Język $L$ jest akceptowany przez deterministyczny automat ze stosem wtw gdy jest akceptowany przez niedeterministyczny automat ze stosem. Źle

c.: Każda gramatyka regularna jest bezkontekstowa. Dobrze

d.: Każdy język bezkontekstowy jest kontekstowy. Dobrze

e.: Język $L$ jest akceptowany przez deterministyczny automat skończenie stanowy wtw gdy jest akceptowany przez niedeterministyczny automat skończenie stanowy. Dobrze

Rozwiązanie

Rodziny $ℒ_{0}$ i $ℒ_{1}$ mają następujące własności:

a.: są zamknięte na sumę Dobrze

b.: są zamknięte na uzupełnienie Źle

c.: są zamknięte na katenację Dobrze

d.: są zamknięte na iloczyn mnogościowy Dobrze

e.: są równe Źle

Rozwiązanie

Wskaż zdania prawdziwe:

a.: każda gramatyka kontekstowa jest rozszerzająca Dobrze

b.: każda gramatyka bezkontekstowa jest rozszerzająca Źle

c.: każda gramatyka regularna jest rozszerzająca Źle

d.: dla każdej gramatyki rozszerzającej istnieje równoważna jej gramatyka kontekstowa Dobrze

e.: dla każdej gramatyki bezkontekstowej istnieje równoważna jej gramatyka rozszerzająca Dobrze

Rozwiązanie

Wskaż zdania prawdziwe:

a.: Istnieje gramatyka rozszerzająca, dla której nie istnieje równoważna jej gramatyka kontekstowa. Źle

b.: Dla dowolnej gramatyki kontekstowej z markerem końca

istnieje równoważna jej gramatyka kontekstowa. Dobrze

c.: Dla dowolnego języka kontekstowego $L$ istnieje automat liniowo ograniczony $𝒜_{L O}$ taki, że $L = L (𝒜_{L O})$ . Dobrze

d.: Iloczyn mnogościowy dwóch języków kontekstowych jest

językiem bezkontekstowym. Źle

e.: Dla dowolnego języka $L$ rozpoznawanego przez automat liniowo ograniczony istnieje gramatyka $G$ taka, że $L = L (G)$ . Dobrze

Rozwiązanie

Wskaż klasy języków domknięte ze względu na iloczyn mnogościowy:

a.: $ℒ_{0}$ Dobrze

b.: $ℒ_{3}$ Dobrze

c.: $ℒ_{2}$ Źle

d.: $ℒ_{1}$ Dobrze

e.: rodzina języków akceptowanych przez automaty skończenie stanowe Dobrze

Rozwiązanie

Klasa $ℒ_{0}$ nie jest zamknięta ze względu na:

a.: sumę Źle

b.: uzupełnienie Dobrze

c.: katenację Źle

d.: gwiazdkę Kleene'ego Źle

e.: przecięcie Źle

Rozwiązanie

Rozważmy język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\{a^n b^n c^n\: n\geq 5\} }

Które z poniższych twierdzeń są prawdziwe:

a.: problem, czy dane $w \in A^{*}$ spełnia $w \in L$ jest nierozstrzygalny Źle

b.: $L \in PSPACE$ Dobrze

c.: $L \in NP$ Dobrze

d.: maszyna Turinga rozpoznająca język $L$ musi być niedeterministyczna lub posiadać $5$ taśm Źle

e.: $L \in P$ Dobrze

Rozwiązanie

Gramatyki typu (0) generują klasę języków:

a.: rekurencyjnych, ale tylko przy założeniu tezy Churcha Źle

b.: zawierającą klasę języków rekurencyjnie przeliczalnych, a przy dodatkowym założeniu tezy Churcha, także klasę języków rekurencyjnych Źle

c.: identyczną z klasą języków rozpoznawalnych przez automat liniowo ograniczony Źle

d.: przy założeniu tezy Churcha, identyczną z klasą języków rozpoznawanych przez deterministyczną maszynę Turinga Dobrze

e.: zawierającą wszystkie języki które są rozpoznawane przez deterministyczną maszynę Turinga, ale istotnie

węższą niż klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga. Źle

Rozwiązanie

Załóżmy, że $L_{1} \propto L_{2}$ oraz dodatkowo $L_{1} \in NP$ . W tej sytuacji:

a.: wprost z definicji transformacji $\propto$ wynika, że $L_{2} \in$ NP Źle

b.: $L_{1} \in$ PSPACE Dobrze

c.: jeśli dodatkowo $L_{1} \in̸ P$ to $L_{2} \in̸ P$ Dobrze

d.: jeśli język $L_{1}$ jest $P$ -zupełny, to $L_{2}$ jest $P$ -trudny Dobrze

e.: wykluczony jest warunek $L_{2} \in PSPACE$ Źle

Rozwiązanie

Które z poniżej wymienionych problemów są nierozstrzygalne:

a.: problem niejednoznaczności dla gramatyk bezkontekstowych Dobrze

b.: problem, czy $L_{1} \cap L_{2} \neq \emptyset$ dla języków regularnych Źle

c.: problem, czy dana gramatyka typu (0) generuje język pusty Dobrze

d.: problem Posta nad alfabetem $A = {1, 2, \dots, n}$ gdzie $n \geq 1$ . Źle

e.: problem, czy $L_{1} \subset L_{2}$ dla języków zadanych przez gramatyki kontekstowe Dobrze

Rozwiązanie

Które z poniższych maszyn są równoważne maszynie Turinga?

a.: maszyna Turinga z wieloma taśmami Dobrze

b.: maszyna Turinga z wieloma głowicami Dobrze

c.: maszyna Turinga z taśmą jednostronnie nieskończoną Dobrze

d.: maszyna Turinga z wieloma taśmami, z których każda jest obustronnie ograniczona Źle

e.: maszyna Turinga niedeterministyczna Dobrze

Rozwiązanie

Stwierdzenie mówiące, iż każda efektywna procedura (algorytm) da się opisać przez pewną maszynę Turinga, znane jest jako:

a.: twierdzenie Kleene'ego Źle

b.: twierdzenie Nerode'a Źle

c.: teza Churcha Dobrze

d.: twierdzenie Savitcha Źle

e.: problem P = NP Źle

Rozwiązanie

111111111111111111111111111111111111111111111111111111111111111 {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:30, 21 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 6: / Linia 6: @@
 ------------------------------
+<quiz>
-{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 kontekstowe i maszyna Turinga - Test}
-{Test wielokrotnego wyboru}
-{{cwiczenie|Czytanie słowa przez automaty||
-<br>
 Wskaż zdania prawdziwe:
 ; a.
-:  Automat liniowo ograniczony może dopisywać literę na
+:  <wrongoption>Automat liniowo ograniczony może dopisywać literę na
-początku lub na końcu czytanego słowa.
+początku lub na końcu czytanego słowa.</wrongoption>
 ; b.
-:  Maszyna Turinga może zmieniać długość czytanego słowa.
+:  <rightoption>Maszyna Turinga może zmieniać długość czytanego słowa.</rightoption>
 ; c.
-:  Automat ze stosem może w jednym przejściu dowolną literę
+:  <wrongoption>Automat ze stosem może w jednym przejściu dowolną literę słowa zapisanego na stosie zastąpić dowolnym słowem nad alfabetem stosu.</wrongoption>
-słowa zapisanego na stosie zastąpić dowolnym słowem nad alfabetem
-stosu.
 ; d.
-:  Automat ze stosem i automat liniowo ograniczony mogą
+:  <rightoption>Automat ze stosem i automat liniowo ograniczony mogą
-zmieniać stan bez czytania litery.
+zmieniać stan bez czytania litery.</rightoption>
 ; e.
-:  Automat liniowo ograniczony może w czytanym słowie
+:  <wrongoption>Automat liniowo ograniczony może w czytanym słowie
-zmieniać dowolną literę z alfabetu taśmy
+zmieniać dowolną literę z alfabetu taśmy</wrongoption>
-}}
+</quiz>
 <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">
@@ Linia 55: / Linia 32: @@
 </div></div>
-{{cwiczenie|Gramatyki i automaty||
-<br>
+<quiz>
 Wskaż zdania prawdziwe:
 ; a.
-:  Każda gramatyka bezkontekstowa jest kontekstowa.
+:  <wrongoption>Każda gramatyka bezkontekstowa jest kontekstowa.</wrongoption>
 ; b.
-:  Język <math>\displaystyle L</math> jest akceptowany przez deterministyczny automat
+:  <wrongoption>Język <math>\displaystyle L</math> jest akceptowany przez deterministyczny automat ze stosem wtw gdy jest akceptowany przez niedeterministyczny automat ze stosem.</wrongoption>
-ze stosem wtw gdy jest akceptowany przez niedeterministyczny automat
-ze stosem.
 ; c.
-:  Każda gramatyka regularna jest bezkontekstowa.
+:  <rightoption>Każda gramatyka regularna jest bezkontekstowa.</rightoption>
 ; d.
-:  Każdy język bezkontekstowy jest kontekstowy.
+:  <rightoption>Każdy język bezkontekstowy jest kontekstowy.</rightoption>
 ; e.
-:  Język <math>\displaystyle L</math> jest akceptowany przez deterministyczny automat
+:  <rightoption>Język <math>\displaystyle L</math> jest akceptowany przez deterministyczny automat skończenie stanowy wtw gdy jest akceptowany przez niedeterministyczny automat skończenie stanowy.</rightoption>
-skończenie stanowy wtw gdy jest akceptowany przez
-niedeterministyczny automat skończenie stanowy.
-}}
+</quiz>
 <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">
@@ Linia 85: / Linia 58: @@
 </div></div>
-{{cwiczenie|Rodziny <math>\displaystyle \mathcal{L}_0</math> i <math>\displaystyle \mathcal{L}_1</math>||
-<br>
+<quiz>
 Rodziny <math>\displaystyle \mathcal{L}_0</math> i <math>\displaystyle \mathcal{L}_1</math> mają następujące
 własności:
 ; a.
-:  są zamknięte na sumę
+:  <rightoption>są zamknięte na sumę</rightoption>
 ; b.
-:  są zamknięte na uzupełnienie
+:  <wrongoption>są zamknięte na uzupełnienie</wrongoption>
 ; c.
-:  są zamknięte na katenację
+: <rightoption>są zamknięte na katenację</rightoption>
 ; d.
-:  są zamknięte na iloczyn mnogościowy
+:  <rightoption>są zamknięte na iloczyn mnogościowy</rightoption>
 ; e.
-:  są równe
+:  <wrongoption>są równe</wrongoption>
-}}
+</quiz>
 <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">
@@ Linia 112: / Linia 85: @@
 </div></div>
-{{cwiczenie|Gramatyki rozszerzające||
-<br>
+<quiz>
 Wskaż zdania prawdziwe:
 ; a.
-:  każda gramatyka kontekstowa jest rozszerzająca
+:  <rightoption>każda gramatyka kontekstowa jest rozszerzająca</rightoption>
 ; b.
-:  każda gramatyka bezkontekstowa jest rozszerzająca
+:  <wrongoption>każda gramatyka bezkontekstowa jest rozszerzająca</wrongoption>
 ; c.
-:  każda gramatyka regularna jest rozszerzająca
+:  <wrongoption>każda gramatyka regularna jest rozszerzająca</wrongoption>
 ; d.
-:  dla każdej gramatyki rozszerzającej istnieje równoważna jej
+:  <rightoption>dla każdej gramatyki rozszerzającej istnieje równoważna jej gramatyka kontekstowa</rightoption>
-gramatyka kontekstowa
 ; e.
-:  dla każdej gramatyki bezkontekstowej istnieje równoważna
+:  <rightoption>dla każdej gramatyki bezkontekstowej istnieje równoważna jej gramatyka rozszerzająca</rightoption>
-jej gramatyka rozszerzająca
-}}
+</quiz>
 <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">
@@ Linia 140: / Linia 111: @@
 </div></div>
-{{cwiczenie|Gramatyki kontekstowe||
-<br>
+<quiz>
 Wskaż zdania prawdziwe:
 ; a.
-:  Istnieje gramatyka rozszerzająca, dla której nie istnieje
+:  <wrongoption>Istnieje gramatyka rozszerzająca, dla której nie istnieje równoważna jej gramatyka kontekstowa.</wrongoption>
-równoważna jej gramatyka kontekstowa.
 ; b.
-:  Dla dowolnej gramatyki kontekstowej z markerem końca
+:  <rightoption>Dla dowolnej gramatyki kontekstowej z markerem końca
-istnieje równoważna jej gramatyka kontekstowa.
+istnieje równoważna jej gramatyka kontekstowa.</rightoption>
 ; c.
-:  Dla dowolnego języka kontekstowego <math>\displaystyle L</math> istnieje automat
+:  <rightoption>Dla dowolnego języka kontekstowego <math>\displaystyle L</math> istnieje automat liniowo ograniczony <math>\displaystyle \mathcal{A}_{LO}</math> taki, że <math>\displaystyle L=L(\mathcal{A}_{LO})</math>.</rightoption>
-liniowo ograniczony <math>\displaystyle \mathcal{A}_{LO}</math> taki, że
-<math>\displaystyle L=L(\mathcal{A}_{LO})</math>.
 ; d.
-:  Iloczyn mnogościowy dwóch języków kontekstowych jest
+:  <wrongoption>Iloczyn mnogościowy dwóch języków kontekstowych jest
-językiem bezkontekstowym.
+językiem bezkontekstowym.</wrongoption>
 ; e.
-:  Dla dowolnego języka <math>\displaystyle L</math> rozpoznawanego przez automat
+:  <rightoption>Dla dowolnego języka <math>\displaystyle L</math> rozpoznawanego przez automat liniowo ograniczony istnieje gramatyka <math>\displaystyle G</math> taka, że <math>\displaystyle L=L(G)</math>.</rightoption>
-liniowo ograniczony istnieje gramatyka <math>\displaystyle G</math> taka, że <math>\displaystyle L=L(G)</math>.
-}}
+</quiz>
 <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">
@@ Linia 172: / Linia 139: @@
 </div></div>
-{{cwiczenie|Domknięcie na iloczyn mnogościowy||
-<br>
+<quiz>
 Wskaż klasy języków domknięte ze względu na iloczyn mnogościowy:
 ; a.
-:  <math>\displaystyle \mathcal{L}_0</math>
+:  <rightoption><math>\displaystyle \mathcal{L}_0</math></rightoption>
 ; b.
-:  <math>\displaystyle \mathcal{L}_3</math>
+:  <rightoption><math>\displaystyle \mathcal{L}_3</math></rightoption>
 ; c.
-:  <math>\displaystyle \mathcal{L}_2</math>
+:  <wrongoption><math>\displaystyle \mathcal{L}_2</math></wrongoption>
 ; d.
-:  <math>\displaystyle \mathcal{L}_1</math>
+:  <rightoption><math>\displaystyle \mathcal{L}_1</math></rightoption>
 ; e.
-:  rodzina języków akceptowanych przez automaty skończenie stanowe
+:  <rightoption>rodzina języków akceptowanych przez automaty skończenie stanowe</rightoption>
-}}
+</quiz>
 <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">
@@ Linia 198: / Linia 165: @@
 </div></div>
-{{cwiczenie|Domknięcie klasy <math>\displaystyle \mathcal{L}_0</math>||
-<br>
+<quiz>
 Klasa <math>\displaystyle \mathcal{L}_0</math> nie jest zamknięta ze względu na:
 ; a.
-:  sumę
+:  <wrongoption>sumę</wrongoption>
 ; b.
-:  uzupełnienie
+:  <rightoption>uzupełnienie</rightoption>
 ; c.
-:  katenację
+:  <wrongoption>katenację</wrongoption>
 ; d.
-:  gwiazdkę Kleene'ego
+:  <wrongoption>gwiazdkę Kleene'ego</wrongoption>
 ; e.
-:  przecięcie
+:  <wrongoption>przecięcie</wrongoption>
-}}
+</quiz>
 <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">
@@ Linia 224: / Linia 191: @@
 </div></div>
-{{cwiczenie|Własności pewnego języka||
-<br>
+<quiz>
 Rozważmy język:
 <center><math>\displaystyle
@@ Linia 235: / Linia 202: @@
 ; a.
-:  problem, czy dane <math>\displaystyle w\in A^*</math> spełnia <math>\displaystyle w\in L</math> jest nierozstrzygalny
+:  <wrongoption>problem, czy dane <math>\displaystyle w\in A^*</math> spełnia <math>\displaystyle w\in L</math> jest nierozstrzygalny</wrongoption>
 ; b.
-:  <math>\displaystyle L\in \textbf{PSPACE}</math>
+:  <rightoption><math>\displaystyle L\in \textbf{PSPACE}</math></rightoption>
 ; c.
-:  <math>\displaystyle L\in \textbf{NP}</math>
+:  <rightoption><math>\displaystyle L\in \textbf{NP}</math></rightoption>
 ; d.
-:  maszyna Turinga rozpoznająca język <math>\displaystyle L</math> musi być niedeterministyczna lub posiadać <math>\displaystyle 5</math> taśm
+:  <wrongoption>maszyna Turinga rozpoznająca język <math>\displaystyle L</math> musi być niedeterministyczna lub posiadać <math>\displaystyle 5</math> taśm</wrongoption>
 ; e.
-:  <math>\displaystyle L\in \textbf{P}</math>
+:  <rightoption><math>\displaystyle L\in \textbf{P}</math></rightoption>
-}}
+</quiz>
 <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">
@@ Linia 255: / Linia 222: @@
 </div></div>
-{{cwiczenie|Gramatyki typu ''' (0) '''||
-<br>
+<quiz>
 Gramatyki typu '''(0)''' generują klasę języków:
 ; a.
-:  rekurencyjnych, ale tylko przy założeniu tezy Churcha
+:  <wrongoption>rekurencyjnych, ale tylko przy założeniu tezy Churcha</wrongoption>
 ; b.
-:  zawierającą klasę języków rekurencyjnie przeliczalnych, a przy dodatkowym założeniu tezy Churcha, także klasę języków
+:  <wrongoption>zawierającą klasę języków rekurencyjnie przeliczalnych, a przy dodatkowym założeniu tezy Churcha, także klasę języków rekurencyjnych</wrongoption>
-rekurencyjnych
 ; c.
-:  identyczną z klasą języków rozpoznawalnych przez automat liniowo ograniczony
+:  <wrongoption>identyczną z klasą języków rozpoznawalnych przez automat liniowo ograniczony</wrongoption>
 ; d.
-:  przy założeniu tezy Churcha, identyczną z klasą języków rozpoznawanych przez deterministyczną maszynę Turinga
+:  <rightoption>przy założeniu tezy Churcha, identyczną z klasą języków rozpoznawanych przez deterministyczną maszynę Turinga</rightoption>
 ; e.
-:  zawierającą wszystkie języki które są rozpoznawane przez deterministyczną maszynę Turinga, ale istotnie
+:  <wrongoption>zawierającą wszystkie języki które są rozpoznawane przez deterministyczną maszynę Turinga, ale istotnie
-węższą niż klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga.
+węższą niż klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga.</wrongoption>
-}}
+</quiz>
 <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">
@@ Linia 283: / Linia 249: @@
 </div></div>
-{{cwiczenie|Złożoności dla języków||
-<br>
+<quiz>
 Załóżmy, że <math>\displaystyle L_1 \propto L_2</math> oraz dodatkowo <math>\displaystyle L_1 \in
 \textbf{NP}</math>. W tej sytuacji:
 ; a.
-:  wprost z definicji transformacji <math>\displaystyle \propto</math> wynika, że <math>\displaystyle L_2 \in  </math> '''NP'''
+:  <wrongoption>wprost z definicji transformacji <math>\displaystyle \propto</math> wynika, że <math>\displaystyle L_2 \in  </math> '''NP''' </wrongoption>
 ; b.
-:  <math>\displaystyle L_1 \in  </math> '''PSPACE'''
+:  <rightoption><math>\displaystyle L_1 \in  </math> '''PSPACE''' </rightoption>
 ; c.
-:  jeśli dodatkowo <math>\displaystyle L_1 \not\in \textbf{P}</math> to <math>\displaystyle L_2 \not\in \textbf{P}</math>
+:  <rightoption>jeśli dodatkowo <math>\displaystyle L_1 \not\in \textbf{P}</math> to <math>\displaystyle L_2 \not\in \textbf{P}</math></rightoption>
 ; d.
-:  jeśli język <math>\displaystyle L_1</math> jest <math>\displaystyle \textbf{P}</math>-zupełny, to <math>\displaystyle L_2</math> jest <math>\displaystyle \textbf{P}</math>-trudny
+:  <rightoption>jeśli język <math>\displaystyle L_1</math> jest <math>\displaystyle \textbf{P}</math>-zupełny, to <math>\displaystyle L_2</math> jest <math>\displaystyle \textbf{P}</math>-trudny</rightoption>
 ; e.
-:  wykluczony jest warunek <math>\displaystyle L_2 \in \textbf{PSPACE}</math>
+:  <wrongoption>wykluczony jest warunek <math>\displaystyle L_2 \in \textbf{PSPACE}</math></wrongoption>
-}}
+</quiz>
 <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">
@@ Linia 310: / Linia 276: @@
 </div></div>
-{{cwiczenie|Problemy nierozstrzygalne dla języków i gramatyk||
-<br>
+<quiz>
 Które z poniżej wymienionych problemów są nierozstrzygalne:
 ; a.
-:  problem niejednoznaczności dla gramatyk bezkontekstowych
+:  <rightoption>problem niejednoznaczności dla gramatyk bezkontekstowych</rightoption>
 ; b.
-:  problem, czy <math>\displaystyle L_1\cap L_2\neq \emptyset</math> dla języków regularnych
+:  <wrongoption>problem, czy <math>\displaystyle L_1\cap L_2\neq \emptyset</math> dla języków regularnych</wrongoption>
 ; c.
-:  problem, czy dana gramatyka typu '''(0)''' generuje język pusty
+:  <rightoption>problem, czy dana gramatyka typu '''(0)''' generuje język pusty</rightoption>
 ; d.
-:  problem Posta nad alfabetem <math>\displaystyle A=\{1,2,\dots,n\}</math> gdzie <math>\displaystyle n\geq 1</math>.
+:  <wrongoption>problem Posta nad alfabetem <math>\displaystyle A=\{1,2,\dots,n\}</math> gdzie <math>\displaystyle n\geq 1</math>.</wrongoption>
 ; e.
-:  problem, czy <math>\displaystyle L_1 \subset L_2</math> dla języków zadanych przez gramatyki kontekstowe
+:  <rightoption>problem, czy <math>\displaystyle L_1 \subset L_2</math> dla języków zadanych przez gramatyki kontekstowe</rightoption>
-}}
+</quiz>
 <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">
@@ Linia 336: / Linia 302: @@
 </div></div>
-{{cwiczenie|Równoważne maszyny Turinga||
-<br>
+<quiz>
 Które z poniższych maszyn są równoważne maszynie Turinga?
 ; a.
-:  maszyna Turinga z wieloma taśmami
+:  <rightoption>maszyna Turinga z wieloma taśmami</rightoption>
 ; b.
-:  maszyna Turinga z wieloma głowicami
+:  <rightoption>maszyna Turinga z wieloma głowicami</rightoption>
 ; c.
-:  maszyna Turinga z taśmą jednostronnie nieskończoną
+:  <rightoption>maszyna Turinga z taśmą jednostronnie nieskończoną</rightoption>
 ; d.
-:  maszyna Turinga z wieloma taśmami, z których każda jest
+:  <wrongoption>maszyna Turinga z wieloma taśmami, z których każda jest obustronnie ograniczona</wrongoption>
-obustronnie ograniczona
 ; e.
-:  maszyna Turinga niedeterministyczna
+:  <rightoption>maszyna Turinga niedeterministyczna</rightoption>
-}}
+</quiz>
 <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">
@@ Linia 363: / Linia 328: @@
 </div></div>
-{{cwiczenie|Algorytmy a maszyna Turinga||
-<br>
+<quiz>
 Stwierdzenie mówiące, iż każda efektywna procedura (algorytm) da się
 opisać przez pewną maszynę Turinga, znane jest jako:
 ; a.
-:  twierdzenie Kleene'ego
+:  <wrongoption>twierdzenie Kleene'ego</wrongoption>
 ; b.
-:   twierdzenie Nerode'a
+:   <wrongoption>twierdzenie Nerode'a</wrongoption>
 ; c.
-:  teza Churcha
+:  <rightoption>teza Churcha</rightoption>
 ; d.
-:  twierdzenie Savitcha
+:  <wrongoption>twierdzenie Savitcha</wrongoption>
 ; e.
-:  problem '''P'''<nowiki> =</nowiki>   '''NP'''
+:  <wrongoption>problem '''P'''<nowiki> =</nowiki>   '''NP'''</wrongoption>
-}}
+</quiz>
 <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">