Test GR

---

Wskaż zdania prawdziwe:

Automat liniowo ograniczony może dopisywać literę na początku lub na końcu czytanego słowa. Źle

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

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

Automat ze stosem i automat liniowo ograniczony mogą zmieniać stan bez czytania litery. Dobrze

Automat liniowo ograniczony może w czytanym słowie zmieniać dowolną literę z alfabetu taśmy Źle

Wskaż zdania prawdziwe:

Każda gramatyka bezkontekstowa jest kontekstowa. Źle

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

Każda gramatyka regularna jest bezkontekstowa. Dobrze

Każdy język bezkontekstowy jest kontekstowy. Dobrze

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

Rodziny ${{ℒ}}_0$ i ${{ℒ}}_1$ mają następujące własności:

są zamknięte na sumę Dobrze

są zamknięte na uzupełnienie Źle

są zamknięte na katenację Dobrze

są zamknięte na iloczyn mnogościowy Dobrze

są równe Źle

Wskaż zdania prawdziwe:

każda gramatyka kontekstowa jest rozszerzająca Dobrze

każda gramatyka bezkontekstowa jest rozszerzająca Źle

każda gramatyka regularna jest rozszerzająca Źle

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

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

Wskaż zdania prawdziwe:

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

Dla dowolnej gramatyki kontekstowej z markerem końca istnieje równoważna jej gramatyka kontekstowa. Dobrze

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

Iloczyn mnogościowy dwóch języków kontekstowych jest językiem bezkontekstowym. Źle

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

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

${{ℒ}}_0$ Dobrze

${{ℒ}}_3$ Dobrze

${{ℒ}}_2$ Źle

${{ℒ}}_1$ Dobrze

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

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

sumę Źle

uzupełnienie Dobrze

katenację Źle

gwiazdkę Kleene'ego Źle

przecięcie Źle

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:

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

$L\in \text{<mrow data-mjx-texclass="ORD">PSPACE</mrow>}$ Dobrze

$L\in \text{<mrow data-mjx-texclass="ORD">NP</mrow>}$ Dobrze

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

$L\in \text{P}$ Dobrze

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

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

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

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

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

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

Załóżmy, że $L_1\propto L_2$ oraz dodatkowo $L_1\in \text{<mrow data-mjx-texclass="ORD">NP</mrow>}$. W tej sytuacji:

wprost z definicji transformacji $\propto$ wynika, że $L_2\in$ NP Źle

$L_1\in$ PSPACE Dobrze

jeśli dodatkowo $L_1\in ̸\text{P}$ to $L_2\in ̸\text{P}$ Dobrze

jeśli język $L_1$ jest $\text{P}$-zupełny, to $L_2$ jest $\text{P}$-trudny Dobrze

wykluczony jest warunek $L_2\in \text{<mrow data-mjx-texclass="ORD">PSPACE</mrow>}$ Źle

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

problem niejednoznaczności dla gramatyk bezkontekstowych Dobrze

problem, czy $L_1\cap L_2\ne \mathrm{\varnothing }$ dla języków regularnych Źle

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

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

problem, czy $L_1\subset L_2$ dla języków zadanych przez gramatyki kontekstowe Dobrze

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

maszyna Turinga z wieloma taśmami Dobrze

maszyna Turinga z wieloma głowicami Dobrze

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

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

maszyna Turinga niedeterministyczna Dobrze

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

twierdzenie Kleene'ego Źle

twierdzenie Nerode'a Źle

teza Churcha Dobrze

twierdzenie Savitcha Źle

problem P = NP Źle

111111111111111111111111111111111111111111111111111111111111111

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}\}} Źle

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

b,d,e

{{cwiczenie|Języki Dycka i Łukasiewicza||

Wskaż zdania prawdziwe:

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

b, e

{{cwiczenie|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}\}} Źle

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

b

{{cwiczenie|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.

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

b.

$1$ Źle

c.

$b^7$ Dobrze

d.

$bca$ Źle

e.

$bcabb$ Dobrze

Rozwiązanie

a, c, e

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

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\}$ Źle

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\}$ Źle

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

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

Rozwiązanie

a, d, e

{{cwiczenie|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 $(aa{)}^{+}(aaa{)}^{+}$ Dobrze

b.

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

c.

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

d.

jest jednoznaczna Źle

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

Rozwiązanie

a, c

{{cwiczenie|Jednoznaczność języków||

Wskaż zdania prawdziwe:

a.

każda gramatyka regularna jest jednoznaczna Źle

b.

każdy język jednoznaczny jest deterministyczny Źle

c.

każdy język regularny jest jednoznaczny Dobrze

d.

każdy język deterministyczny jest jednoznaczny Dobrze

e.

język jest jednoznaczny wtw gdy jest deterministyczny Źle

Rozwiązanie

c, d

{{cwiczenie|Postać normalna Greibach i Chomsky'ego||

Wskaż zdania prawdziwe:

a.

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

b.

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

c.

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

d.

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

e.

Każda gramatyka w postaci normalnej Chomsky'ego jest

właściwa. Dobrze

Rozwiązanie

a,e

{{cwiczenie|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. Dobrze

b.

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

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

d.

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

e.

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

Rozwiązanie

a,b,c,e

{{cwiczenie|Zamkniętość rodziny języków bezkontekstowych||

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

a.

homomorfizm Dobrze

b.

iloczyn mnogościowy Źle

c.

uzupełnienie Źle

d.

gwiazdkę Kleene'ego Dobrze

e.

katenację Dobrze

Rozwiązanie

a,d,e

{{cwiczenie|Języki generowane gramatykami bezkontekstowymi||

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:

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

a,e

{{cwiczenie|Problemy rozstrzygalne dla języków bezkontekstowych||

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

a.

$w\in L$ Dobrze

b.

$L=\mathrm{\varnothing }$ Dobrze

c.

nieskończoność $L$ Dobrze

d.

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

e.

jednoznaczność gramatyki bezkontekstowej Źle

Rozwiązanie

a,b,c

{{cwiczenie|Klasy języków||

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

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

a,b,d

{{cwiczenie|Języki deterministyczne||

Wskaż języki deterministyczne:

a.

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

b.

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

c.

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

d.

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

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

Rozwiązanie

b,c,e

{{cwiczenie|Języki niejednoznaczne||

Wskaż języki niejednoznaczne:

a.

$\{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

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

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\}} Źle

d.

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

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\}} Źle

Rozwiązanie

a,b,d

{{cwiczenie|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 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\}$:

a.

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

b.

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

c.

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

d.

jest automatem deterministycznym Dobrze

e.

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

Rozwiązanie

a,d

{{cwiczenie|Problemy nierozstrzygalne w klasie ${{ℒ}}_2$||

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

a.

$w\in L$ Źle

b.

jednoznaczność $L$ Dobrze

c.

$L_1=L_2$ Dobrze

d.

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

e.

nieskończoność $L$ Źle

Rozwiązanie

b,c

{{cwiczenie|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 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\}$:

a.

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

b.

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

c.

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

d.

jest automatem deterministycznym Dobrze

e.

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

Rozwiązanie

c,d

{{cwiczenie|Algorytm CYK||

Algorytm Cocke'a-Youngera-Kasamiego:

a.

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

b.

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

c.

jest niedeterministyczny Źle

d.

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

e.

działa w oparciu o zasadę programowania dynamicznego Dobrze

Rozwiązanie

a, e

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:

$abbaaa\in \{aa,bb{\}}^{*}$ Źle

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

$abbaaa\in \{abb,a{\}}^{*}$ Dobrze

$abbaaa\in \{ba,ab{\}}^{*}$ Źle

$abbaaa\in \{aa,ab,ba{\}}^{*}$ 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)=3x$ Źle

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

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)} , $h(x)=3x$ Ź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 $RS=(\{a,b,c\},\{(a,b),(b,c),(b,a),(cc,b))$ oraz niech $I=\{ccb\}$. Wskaż stwierdzenia prawdziwe:

$abc\in L_{gen}(RS,I)$ Źle

$ccb\in L_{gen}(RS,I)$ Dobrze

$bb\in L_{gen}(RS,I)$ Dobrze

$aab\in L_{gen}(RS,I)$ Źle

$aa\in L_{gen}(RS,I)$ Dobrze

Wyrażenie regularne

$((aa+bb{)}^{*}(ab+ba)(aa+bb{)}^{*}(ab+ba){)}^{*}(aa+bb{)}^{*}$

reprezentuje język:

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

$\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w-{\mathrm{♯}}_{b}w=0(mod2)\}$ Źle

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

$\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w-{\mathrm{♯}}_{b}w=1(mod2)\}$ Źle

$\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w=4k$, ${\mathrm{♯}}_{b}w=4l$, $k,l\ge 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^{*}\mathrm{\setminus }L=b{A}^{*}b+b$ Źle

$A^{*}\mathrm{\setminus }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+aa)b^{*}{)}^{*}$ Źle

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

$(b+ab+aab{)}^{*}+(b+ab+aab{)}^{*}a+(b+ab+aab{)}^{*}aa$ Dobrze

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

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

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

Istnieje liczba naturalna $N\ge 1$ taka, że każde słowo $w\in L$ o długości $|w|\ge 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 $\varphi :A^{*}\to M$ taki, że ${\varphi }^{-1}(\varphi (L))=L$. Dobrze

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

kongruencji

$\rho$

na

$A^{*}$

:

$L={\cup }_{w\in L}[w{]}_{\rho }.$

Ź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{\}}^{*}:{\mathrm{♯}}_{a}w=2k,{\mathrm{♯}}_{b}w=2l+1$, $k,l\ge 0\}$ Źle

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

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

rozpoznaje język $\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w=2k+1,{\mathrm{♯}}_{b}w=2l+1$, $k,l\ge 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

$(rs{)}^{*}r=r(sr{)}^{*}$ Dobrze

Wskaż języki regularne:

$\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w={\mathrm{♯}}_{b}w(mod3)\}$ Dobrze

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

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

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

$\{a^n:n=3k$ lub $n=5k,k\ge 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=vbu$ zachodzi ${\mathrm{♯}}_{a}v=2k$ dla pewnego $k\ge 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 ${{𝒜}}_{ND}=(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$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$	$\{q_1\}$

Wskaż zdania prawdziwe:

$L({{𝒜}}_{ND})=a^2(a+ba{)}^{*}$. Dobrze

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

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

$L({{𝒜}}_{ND})=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$

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

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

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

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

$(\{{\tau }_{{𝒜}}(a),{\tau }_{{𝒜}}(b),{\tau }_{{𝒜}}(ab),{\tau }_{{𝒜}}(ba)\},\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=\mathrm{\varnothing }$ Dobrze

nieskończoność $L_1$ Dobrze

$L_1=\mathrm{\varnothing }$ 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