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:

a.

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

b.

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

c.

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)} ,

$h(x)=3x$

d.

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

$h(b)=a{b}^2$

e.

Parser nie mógł rozpoznać (nieznana funkcja „\mathds”): {\displaystyle \displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+)} , $h(a)=1$,

$h(b)=1$

Rozwiązanie

b, d, e

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:

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

b, c, e

Wyrażenie regularne

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

reprezentuje 

język:

a.

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

$k,l>0\}$

b.

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

c.

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

d.

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

e.

$\{w\in \{a,b{\}}^{*}:{\mathrm{♯}}_{a}w=4k$, ${\mathrm{♯}}_{b}w=4l$, $k,l\ge 0\}$

Rozwiązanie

a

Niech $A=\{a,b\}$ oraz $L=a{A}^{*}a$. Wskaż zdania prawdziwe:

a.

minimalny automat akceptujący $L$ ma 5 stanów

b.

ilość klas równoważności prawej kongruencji syntaktycznej

$P_L^r$ wyznaczonej przez $L$ jest równa 4

c.

$A^{*}\mathrm{\setminus }L=b{A}^{*}b+b$

d.

$A^{*}\mathrm{\setminus }L=b{A}^{*}+a{A}^{*}b+a+1$

e.

monoid przejśc minimalnego automatu akceptującego $L$ ma 6

elementów

Rozwiązanie

b, d, e

Niech $L$ będzie dowolnym językiem regularnym. Wskaż zdania prawdziwe:

a.

$L$ jest rozpoznawany przez pewien niedeterministyczny

automat skończenie stanowy z pustymi przejściami

b.

$L$ jest rozpoznawany przez automat deterministyczny

skończenie stanowy

c.

$L$ jest rozpoznawany przez niedeterministyczny automat

z pustymi przejściami o jednoelementowym zbiorze stanów początkowych

d.

Nie istnieje automat niedeterministyczny z pustymi

przejściami rozpoznający $L$ i taki, że zbiór stanów początkowych jest jednoelementowy

e.

Nie istnieje gramatyka lewoliniowa generująca $L$

Rozwiązanie

a, b, c

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

a.

$n_1\cdot n_2$ stanów

b.

$O(n_1+n_2)$ stanów

c.

$n_1$ stanów

d.

$n_2$ stanów

e.

3 stany

Rozwiązanie

a, b

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

a.

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

b.

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

c.

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

d.

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

e.

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

Rozwiązanie

c, d, e

Ćwiczenie Języki regularne - warunki równoważne

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

a.

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

b.

Istnieje skończony monoid $M$ i homomorfizm $\varphi :A^{*}\to M$ taki, że ${\varphi }^{-1}(\varphi (L))=L$.

c.

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

kongruencji $\rho$ na $A^{*}$: $L={\cup }_{w\in L}[w{]}_{\rho }.$

d.

$L\in {ℛ}{ℰ}{𝒢}(A^{*})$.

e.

$L$ jest akceptowany przez deterministyczny automat

skończenie stanowy z jednym stanem końcowym.

Rozwiązanie

b,d

Ćwiczenie Automat skończenie stanowy

Automat ${𝒜}=(S,A,s_0,f,F)$, gdzie $S=\{s_0,s_1,s_2,s_3\}$, $A=\{a,b\}$, $F=\{s_1\}$, {

{

Rozwiązanie

a,d

Ćwiczenie Równość wyrażeń regularnych

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

Ćwiczenie Języki regularne

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

Ćwiczenie Automat skończenie stanowy

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

{

{

Rozwiązanie

a,c

Ćwiczenie Automat niedeterministyczny

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

{

{

Rozwiązanie

a,b,e

Ćwiczenie Równość ${ℛ}{ℰ}{𝒞}(A^{*})={ℛ}{ℰ}{𝒢}(A^{*})$

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

Ćwiczenie Monoid przejść

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

{

{

Rozwiązanie

a

Ćwiczenie Problemy rozstrzygalne

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

Ćwiczenie Algorytm determinizacji automatu

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