Języki, automaty i obliczenia/Test 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne

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

$({\mathbb{\mathbb{Z}}}_{mod2},\cdot )$ Dobrze

$({\mathbb{\mathbb{N}}}_1,+)$, gdzie ${\mathbb{\mathbb{N}}}_1=\{1,2,3,...\}$ Źle

$({\mathbb{\mathbb{N}}}_p,+)$, gdzie ${\mathbb{\mathbb{N}}}_p$ jest zbiorem wszystkich liczb pierwszych Źle

$(\mathbb{ℝ},\cdot )$ Dobrze

$(\mathbb{\mathbb{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:

$h:(\mathbb{ℝ},+)\to (\mathbb{\mathbb{Z}},+)$, $h(x)=3x$ Źle

$h:(\mathbb{ℝ},+)\to (\mathbb{ℝ},+)$, $h(x)=3x$ Dobrze

$h:(\mathbb{ℝ},\cdot )\to (\mathbb{ℝ},\cdot )$, $h(x)=3x$ Źle

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

$h:\{a,b{\}}^{*}\to (\mathbb{\mathbb{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