Test GR

---

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

Uzupelnij tytul

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

}

a.

jest automatem minimalnym

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

a,d

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

a.

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

b.

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

c.

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

d.

$r+r=r$

e.

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

Rozwiązanie

a,c,d,e

Wskaż języki regularne:

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

a,d,e

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

{

Uzupelnij tytul

$f$	$s_0$	$s_1$	$s_2$
$a$	$s_1$	$s_0$	$s_2$
$b$	$s_0$	$s_2$	$s_2$

}

Wskaż zdania prawdziwe:

a.

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

b.

Równoważny automat minimalny ma 2 stany.

c.

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

d.

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

e.

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

słowa $w$.

Rozwiązanie

a,c

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

{

Uzupelnij tytul

$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:

a.

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

b.

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

c.

Równoważny automat deterministyczny posiada 3 stany.

d.

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

e.

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

Rozwiązanie

a,b,e

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:

a.

twierdzenie Nerode'a

b.

teza Churcha

c.

lemat Ardena

d.

lemat o pompowaniu

e.

twierdzenie Kleene'ego

Rozwiązanie

e

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

{

Uzupelnij tytul

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

}

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

a

Niech $L_1,L_2$ będą językami regularnymi. Wskaż problemy rozstrzygalne.

a.

$w\in L_1$

b.

$w\in L_1\cap L_2$

c.

$L_1\cap L_2=\mathrm{\varnothing }$

d.

nieskończoność $L_1$

e.

$L_1=\mathrm{\varnothing }$

Rozwiązanie

a,b,c,d,e

Algorytm determinizacji automatu:

a.

jest deterministyczny

b.

działa w czasie wielomianowym

c.

może się zapętlić

d.

działa w czasie eksponencjalnym

e.

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

automat deterministyczny

Rozwiązanie

a, d

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