Języki, automaty i obliczenia/Test 11: Automat ze stosem

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

$L_1=\{a^k{b}^l:k,l\in \mathbb{\mathbb{N}}\}$ Źle

$L_2=\{a^k{b}^k:k\in \mathbb{\mathbb{N}}\}$ Dobrze

$L_3=\{a^{k}c{b}^l:k,l\in \mathbb{\mathbb{N}}\}$ Źle

$L_4=\{a^{k}c{b}^k:k\in \mathbb{\mathbb{N}}\}$ Dobrze

$L_5=\{w\in \{a,b{\}}^{*}:w=\overleftarrow{w}\}$ Dobrze

Wskaż zdania prawdziwe:

Istnieje gramatyka reularna generująca język Dycka. Źle

Język Dycka jest bezkontekstowy i nie jest regularny. Dobrze

Istnieje automat skończenie stanowy rozpoznający język Łukasiewicza. Źle

Język Łukasiewicza da się opisać wyrażeniem regularnym. Źle

Istnieje gramatyka bezkontekstowa bez symboli bezużytecznych generująca język Dycka. Dobrze

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

$L_1=\{a^k{b}^l:k,l\in \mathbb{\mathbb{N}}\}$ Źle

$L_2=\{a^k{b}^n{c}^m:k<n<m\}$ Dobrze

$L_3=\{a^n{b}^n:n\in \mathbb{\mathbb{N}}\}$ Źle

$L_4=\{c{a}^n{b}^n:n\in \mathbb{\mathbb{N}}\}$ Źle

$L_5=\{w\overleftarrow{w}{a}^{|w|}:w\in \{a,b{\}}^{*}\}$ Dobrze

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

$\begin{array}{rl}{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{array}$

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

$ca{b}^{2}abab$ Dobrze

$1$ Źle

$b^7$ Dobrze

$bca$ Źle

$bcabb$ Dobrze

Wskaż gramatyki $G=(V,A,v_0,P)$ niejednoznaczne:

$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|ba\}$ Dobrze

$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$, $v_2\to b{v}_{2}a|b$, $v_3\to b{v}_{2}c\}$ Źle

$V=\{v_0,v_1\},A=\{a,b\}$, $P=\{v_0\to v_0{v}_1|b$, $v_1\to a{v}_{1}b|b\}$ Źle

$V=\{v_0,...,v_5\}$, $A=\{a\}$, $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\}$ Dobrze

$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$, $v_2\to v_{2}b|b|v_3$, $v_3\to b{v}_{3}a|ba|b\}$ Dobrze

Gramatyka $G=(V_N,V_T,v_0,P)$, gdzie $V_N=\{v_0,\dots ,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\}$:

generuje język $(aa{)}^{+}+(aaa{)}^{+}$ Dobrze

generuje język $(aa+aaa{)}^{+}$ Źle

jest równoważna gramatyce $G^{\prime }=({V_N}^{\prime },V_T,v_0,P^{\prime })$, gdzie ${V_N}^{\prime }=\{v_0,...,v_6\}$, $P^{\prime }=\{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$ Dobrze

jest jednoznaczna Źle

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

Wskaż zdania prawdziwe:

każda gramatyka regularna jest jednoznaczna Źle

każdy język jednoznaczny jest deterministyczny Źle

każdy język regularny jest jednoznaczny Dobrze

każdy język deterministyczny jest jednoznaczny Dobrze

język jest jednoznaczny wtw gdy jest deterministyczny Źle

Wskaż zdania prawdziwe:

Każda gramatyka w postaci normalnej Chomsky'ego jest bezkontekstowa. Dobrze

Jeśli gramatyka bezkontekstowa $G$ ma $n$ produkcji, to równoważna jej gramatyka $G^{\prime }$ w postaci normalnej Greibach ma co najwyżej $2n$ produkcji. Źle

Każdą gramatykę bezkontekstową można przekształcić do postaci normalnej Greibach. Źle

Żadna gramatyka w postaci normalnej Greibach nie jest regularna. Źle

Każda gramatyka w postaci normalnej Chomsky'ego jest właściwa. Dobrze

Wskaż zdania prawdziwe:

Każdy automat ze stosem akceptujący przez pusty stos posiada równoważny automat ze stosem akceptujący przez stany końcowe. Dobrze

Każdy język bezkontekstowy jest akceptowany przez pusty stos przez jednostanowy automat ze stosem. Dobrze

Każdy automat ze stosem, w którym wielkość stosu jest ograniczona przez pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu. Dobrze

Każdy automat ze stosem posiada równoważny deterministyczny automat ze stosem. Źle

Każdy automat ze stosem akceptujący przez stany końcowe posiada równoważny automat ze stosem akceptujący przez pusty stos. Dobrze

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

homomorfizm Dobrze

iloczyn mnogościowy Źle

uzupełnienie Źle

gwiazdkę Kleene'ego Dobrze

katenację Dobrze

Dane są dwie gramatyki: dla

$i=1,2G_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:

$L(G_1)\cap L(G_2)\in ̸{{ℒ}}_2$ Dobrze

$L(G_1)\cap L(G_2)$ jest językiem skończonym Źle

$L(G_1)=L(G_2)$ Źle

$L(G_1)\subset L(G_2)$ Źle

$L(G_1)\cup L(G_2)\in {{ℒ}}_2$ Dobrze

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

$w\in L$ Dobrze

$L=\mathrm{\varnothing }$ Dobrze

nieskończoność $L$ Dobrze

równoważność dwóch gramatyk bezkontekstowych Źle

jednoznaczność gramatyki bezkontekstowej Źle

Niech $L\in {{ℒ}}_2$, $R\in {{ℒ}}_3$. Wówczas:

$L\cap R\in {{ℒ}}_2$ Dobrze

$L\mathrm{\setminus }R\in {{ℒ}}_2$ Dobrze

$\bar{L}\in {{ℒ}}_2$ Źle

$L\cap \bar{R}\in {{ℒ}}_2$ Dobrze

$\bar{L}\cap R\in {{ℒ}}_2$ Źle

Wskaż języki deterministyczne:

$\{a^n{b}^n:n\ge 1\}\cup \{a^n{b}^{3n}:n\ge 1\}$ Źle

$\{a^{2n}:n\ge 1\}\cup \{a^{3n}:n\ge 1\}$ Dobrze

$\{a^n{b}^{n+m}{c}^m:m,n\ge 1\}$ Dobrze

$\{wx\overleftarrow{w}:w\in \{a,b{\}}^{*},x\in \{a,b\}\}$ Źle

$\{a^n{b}^n{a}^m{b}^p:n,m,p\ge 1\}\cup \{a^n{b}^m{a}^p{b}^p:n,m,p\ge 1\}$ Dobrze

Wskaż języki niejednoznaczne:

$\{a^n{b}^n{c}^m{d}^m:n,m\ge 1\}\cup \{a^n{b}^m{c}^m{d}^n:n,m\ge 1\}$ Dobrze

$\{a^n{b}^m{c}^n{d}^p:n,m,p\ge 1\}\cup \{a^n{b}^m{c}^p{d}^m:n,m,p\ge 1\}$ Dobrze

$\{a^n{b}^n{a}^m{b}^p:n,m,p\ge 1\}\cup \{a^n{b}^m{a}^p{b}^p:n,m,p\ge 1\}$ Źle

$\{a^n{b}^m{c}^m:n,m\ge 1\}\cup \{a^n{b}^n{c}^m:n,m\ge 1\}$ Dobrze

$\{a^n{b}^m{c}^m{d}^p:n,m,p\ge 1\}\cup \{a^n{b}^m{c}^p{d}^n:n,m,p\ge 1\}$ Źle

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 za{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 za{q}_1$, $a{q}_{1}b\to a^2{q}_1$, $a{q}_{1}c\to 1q_2$, $a{q}_{2}c\to 1q_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\}$:

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

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

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

jest automatem deterministycznym Dobrze

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

Niech $L,L_1,L_2\in {{ℒ}}_2$. Wskaż problemy nierozstrzygalne w klasie ${{ℒ}}_2$:

$w\in L$ Źle

jednoznaczność $L$ Dobrze

$L_1=L_2$ Dobrze

$L=\mathrm{\varnothing }$ Źle

nieskończoność $L$ Źle

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 aa{q}_0$, $a{q}_{0}b\to 1q_0$, $z_0{q}_{0}b\to z_{0}b{q}_1$, $b{q}_{1}b\to bb{q}_1$, $b{q}_{1}a\to 1q_1$, $z_0{q}_1\to z_0{q}_0\}$:

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

rozpoznaje język $\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w\le {\mathrm{♯}}_{b}w\}$ Źle

rozpoznaje język $\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w\ge {\mathrm{♯}}_{b}w\}$ Dobrze

jest automatem deterministycznym Dobrze

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

Algorytm Cocke'a-Youngera-Kasamiego:

sprawdza, czy słowo należy do języka bezkontekstowego Dobrze

działa w czasie $O(n^2\log n)$ Źle

jest niedeterministyczny Źle

może dostać na wejście dowolną gramatykę bezkontekstową Źle

działa w oparciu o zasadę programowania dynamicznego Dobrze