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

From Studia Informatyczne

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

\displaystyle (\mathds{Z}_{mod\ 2}, \cdot)

\displaystyle (\mathds{N}_1, +), gdzie \displaystyle \mathds{N}_1=\{1,2,3,...\}

\displaystyle (\mathds{N}_p,+), gdzie \displaystyle \mathds{N}_p jest zbiorem wszystkich liczb pierwszych

\displaystyle (\mathds{R}, \cdot)

\displaystyle (\mathds{Z}, +)


Wskaż stwierdzenia prawdziwe:

\displaystyle abbaaa \in \{aa,bb\}^*

\displaystyle abbaaa \in \{a,b\}^*

\displaystyle abbaaa \in \{abb,a\}^*

\displaystyle abbaaa \in \{ba, ab\}^*

\displaystyle abbaaa \in \{aa, ab, ba\}^*


Wskaż, które z poniższych odwzorowań są homomorfizmami:

\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{Z},+), \displaystyle h(x)=3x

\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{R},+), \displaystyle h(x)=3x

\displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot), \displaystyle h(x)=3x

\displaystyle h: \{a,b\}^* \rightarrow \{a,b\}^*, \displaystyle h(a)=a^2, \displaystyle h(b)=ab^2

\displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+), \displaystyle h(a)=1, \displaystyle h(b)=1


Dany niech będzie system przepisujący \displaystyle RS=(\{a,b,c\},  \{(a,b),(b,c),(b,a),(cc,b)) oraz niech \displaystyle I=\{ccb\}. Wskaż stwierdzenia prawdziwe:

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

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

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

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

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


Wyrażenie regularne

\displaystyle ((aa+bb)^*(ab+ba)(aa+bb)^*(ab+ba))^*(aa+bb)^*

reprezentuje język:

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k, \displaystyle \sharp_bw = 2l, \displaystyle k,l >0\}

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 0 (mod 2)\}

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw = 2k, k \geq  0\}

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 1 (mod 2)\}

\displaystyle \{w \in \{a,b\}^*: \sharp_aw = 4k, \displaystyle \sharp_bw = 4l, \displaystyle k,  l \geq 0\}


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

minimalny automat akceptujący \displaystyle L ma 5 stanów

ilość klas równoważności prawej kongruencji syntaktycznej \displaystyle P_L^r wyznaczonej przez \displaystyle L jest równa 4

\displaystyle A^* \backslash L = bA^*b + b

\displaystyle A^* \backslash L = bA^*+aA^*b+a+1

monoid przejśc minimalnego automatu akceptującego \displaystyle L ma 6 elementów


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

\displaystyle L jest rozpoznawany przez pewien niedeterministyczny automat skończenie stanowy z pustymi przejściami

\displaystyle L jest rozpoznawany przez automat deterministyczny skończenie stanowy

\displaystyle L jest rozpoznawany przez niedeterministyczny automat z pustymi przejściami o jednoelementowym zbiorze stanów początkowych

Nie istnieje automat niedeterministyczny z pustymi przejściami rozpoznający \displaystyle L i taki, że zbiór stanów początkowych jest jednoelementowy

Nie istnieje gramatyka lewoliniowa generująca \displaystyle L


Niech \displaystyle L_1, \displaystyle L_2 będą językami rozpoznawanymi odpowiednio przez automaty o \displaystyle n_1 i \displaystyle n_2 stanach. Aby stwierdzić, dla dowolnego słowa \displaystyle w, czy jest ono rozpoznawane przez oba automaty, wystarczy skonstruować odpowiedni automat mający

\displaystyle n_1 \cdot n_2 stanów

\displaystyle O(n_1+n_2) stanów

\displaystyle n_1 stanów

\displaystyle n_2 stanów

3 stany


Język \displaystyle L składa się ze wszystkich słów nad alfabetem \displaystyle A=\{a,b\} nie zawierających podsłowa \displaystyle a^3. Wskaż wyrażenie regularne reprezentujące \displaystyle L:

\displaystyle (b^*(1+a+aa)b^*)^*

\displaystyle (b^*(1+a+aa)bb^*)^*

\displaystyle (b+ab+aab)^*+(b+ab+aab)^*a+(b+ab+aab)^*aa

\displaystyle ((1+a+aa)bb^*)^*(1+a+aa)

\displaystyle b^*(a+aa)bb^*)^*(1+a+aa)


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

Istnieje liczba naturalna \displaystyle N \geq 1 taka, że każde słowo \displaystyle w \in L o długości \displaystyle |w| \geq N można przedstawić jako katenację \displaystyle w = v_1uv_2, gdzie \displaystyle v_1, v_2 \in A^*, \displaystyle u \in A^+ oraz \displaystyle v_1u^*v_2  \subset L.

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

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

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

\displaystyle L \in \mathcal{REG}(A^*).

\displaystyle L jest akceptowany przez deterministyczny automat skończenie stanowy z jednym stanem końcowym.


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

\displaystyle f \displaystyle s_0 \displaystyle s_1 \displaystyle s_2

\displaystyle s_3

\displaystyle a \displaystyle s_1 \displaystyle s_0 \displaystyle s_3 \displaystyle s_2
\displaystyle b \displaystyle s_3 \displaystyle s_2 \displaystyle s_1 \displaystyle s_0

jest automatem minimalnym

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k,  \sharp_bw = 2l+1, \displaystyle k,l \geq 0\}

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k,  \sharp_bw = 2l, \displaystyle k,l \geq 0\}

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k+1,  \sharp_bw = 2l, \displaystyle k,l \geq 0\}

rozpoznaje język \displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k+1,  \sharp_bw = 2l+1, \displaystyle k,l \geq 0\}


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

\displaystyle r^*r^*=r^*

\displaystyle (r+s)^*=r^*+s^*

\displaystyle (r^*+s^*)^*=(r^*s^*)^*

\displaystyle r+r=r

\displaystyle (rs)^*r=r(sr)^*


Wskaż języki regularne:

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\ (mod\ 3)\}

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw\}

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

\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw \cdot \sharp_bw = 100\}

\displaystyle \{a^n:\ n=3k lub \displaystyle   n=5k,\ k \geq 0\}


Dany jest automat \displaystyle \mathcal{A}=(S, A, s_0, f, F), gdzie \displaystyle S=\{s_0,s_1,s_2\}, \displaystyle A=\{a,b\}, \displaystyle F=\{s_0,s_1\},


\displaystyle f \displaystyle s_0 \displaystyle s_1 \displaystyle s_2
\displaystyle a \displaystyle s_1 \displaystyle s_0 \displaystyle s_2
\displaystyle b \displaystyle s_0 \displaystyle s_2 \displaystyle s_2

Wskaż zdania prawdziwe:

\displaystyle L(\mathcal{A})=(a^2+b)^*(a+1).

Równoważny automat minimalny ma 2 stany.

Jeśli \displaystyle w \in L(\mathcal{A}), to dla każdych \displaystyle v,u \in A^* takich, że \displaystyle w=vbu zachodzi \displaystyle \sharp_av = 2k dla pewnego \displaystyle k \geq 0.

\displaystyle a^*b^* \subset L(\mathcal{A}).

Jeśli \displaystyle w \in L(\mathcal{A}), to \displaystyle a^2b jest podsłowem słowa \displaystyle w.


Dany niech będzie automat niedeterministyczny \displaystyle \mathcal{A}_{ND}=(Q,  A, \{q_0\}, f, F), gdzie \displaystyle Q=\{q_0, q_1, q_2\}, \displaystyle A=\{a,b\}, \displaystyle F=\{q_2\},


\displaystyle f \displaystyle q_0 \displaystyle q_1 \displaystyle q_2
\displaystyle a \displaystyle \{q_1\} \displaystyle \{q_0,q_2\} \displaystyle \{q_2\}
\displaystyle b \displaystyle \emptyset \displaystyle \emptyset \displaystyle \{q_1\}

Wskaż zdania prawdziwe:

\displaystyle L(\mathcal{A}_{ND})=a^2(a+ba)^*.

\displaystyle L(\mathcal{A}_{ND})=a(aa^*b)^*aa^*.

Równoważny automat deterministyczny posiada 3 stany.

\displaystyle L(\mathcal{A}_{ND})=a^2(a^*b)^*aa^*.

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


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

teza Churcha

lemat Ardena

lemat o pompowaniu

twierdzenie Kleene'ego


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

\displaystyle f \displaystyle s_0 \displaystyle s_1 \displaystyle s_2 \displaystyle s_3
\displaystyle a \displaystyle s_1 \displaystyle s_0 \displaystyle s_3 \displaystyle s_2
\displaystyle b \displaystyle s_3 \displaystyle s_2 \displaystyle s_1 \displaystyle s_0


\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b),\tau_{\mathcal{A}}(ab)\},  \circ)

\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a)\},\circ)

\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(ab)\},\circ)

\displaystyle (\{\tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b)\},\circ)

\displaystyle (\{\tau_{\mathcal{A}}(a),\tau_{\mathcal{A}}(b),\tau_{\mathcal{A}}(ab),\tau_{\mathcal{A}}(ba)\},  \circ)


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

\displaystyle w \in L_1

\displaystyle w \in L_1 \cap L_2

\displaystyle L_1 \cap L_2 = \emptyset

nieskończoność \displaystyle L_1

\displaystyle L_1 = \emptyset


Algorytm determinizacji automatu:

jest deterministyczny

działa w czasie wielomianowym

może się zapętlić

działa w czasie eksponencjalnym

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


Wskaż zdania prawdziwe:

istnieje algorytm minimalizacji automatu działający w czasie \displaystyle n\log n

żaden algorytm minimalizacji nie może działać szybciej niż w czasie \displaystyle O(n^2)

algorytm minimalizacji zawsze zwróci automat o mniejszej liczbie stanów niż automat podany na wejściu

algorytmy minimalizacji są algorytmami niedeterministycznymi

algorytmy minimalizacji nie działają dla automatów jednostanowych