Test GR: Różnice pomiędzy wersjami

Wersja z 11:33, 14 wrz 2006

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:

$a b b a a a \in {a a, b b}^{*}$ Źle

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

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

$a b b a a a \in {b a, a b}^{*}$ Źle

$a b b a a a \in {a a, a b, b a}^{*}$ 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) = 3 x$ Źle

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

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

$a b c \in L_{g e n} (R S, I)$ Źle

$c c b \in L_{g e n} (R S, I)$ Dobrze

$b b \in L_{g e n} (R S, I)$ Dobrze

$a a b \in L_{g e n} (R S, I)$ Źle

$a a \in L_{g e n} (R S, I)$ Dobrze

Wyrażenie regularne

((a a + b b)^{*} (a b + b a) (a a + b b)^{*} (a b + b a))^{*} (a a + b b)^{*}

reprezentuje

język:

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

${w \in {a, b}^{*} : ♯_{a} w - ♯_{b} w = 0 (m o d 2)}$ Źle

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

${w \in {a, b}^{*} : ♯_{a} w - ♯_{b} w = 1 (m o d 2)}$ Źle

${w \in {a, b}^{*} : ♯_{a} w = 4 k$ , $♯_{b} w = 4 l$ , $k, l \geq 0}$ Źle

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^{*} ∖ L = b A^{*} b + b$

d.: $A^{*} ∖ L = b A^{*} + a A^{*} b + a + 1$

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

elementów

Rozwiązanie

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

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

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 + a a) b^{*})^{*}$

b.: $(b^{*} (1 + a + a a) b b^{*})^{*}$

c.: $(b + a b + a a b)^{*} + (b + a b + a a b)^{*} a + (b + a b + a a b)^{*} a a$

d.: $((1 + a + a a) b b^{*})^{*} (1 + a + a a)$

e.: $b^{*} (a + a a) b b^{*})^{*} (1 + a + a a)$

Rozwiązanie

Ć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 \geq 1$ taka, że każde słowo

$w \in L$ o długości $| w | \geq 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 $ϕ : A^{*} \to M$ taki, że $ϕ^{- 1} (ϕ (L)) = L$ .

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

kongruencji

ρ

na

A^{*}

:

L = \cup_{w \in L} [w]_{ρ} .

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

e.: $L$ jest akceptowany przez deterministyczny automat

skończenie stanowy z jednym stanem końcowym.

Rozwiązanie

Ć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

Ć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.: $(r s)^{*} r = r (s r)^{*}$

Rozwiązanie

Ćwiczenie Języki regularne

Wskaż języki regularne:

a.: ${w \in {a, b}^{*} : ♯_{a} w = ♯_{b} w (m o d 3)}$

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

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

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

e.: ${a^{n} : n = 3 k$ lub $n = 5 k, k \geq 0}$

Rozwiązanie

Ć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

Ćwiczenie Automat niedeterministyczny

Dany niech będzie automat niedeterministyczny $𝒜_{N D} = (Q, A, {q_{0}}, f, F)$ , gdzie $Q = {q_{0}, q_{1}, q_{2}}$ , $A = {a, b}$ , $F = {q_{2}}$ ,

{

Rozwiązanie

Ć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

Ćwiczenie Monoid przejść

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

{

Rozwiązanie

Ć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} = \emptyset$

d.: nieskończoność $L_{1}$

e.: $L_{1} = \emptyset$

Rozwiązanie

Ć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

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

@@ Linia 32: / Linia 32: @@
 <rightoption reply="Dobrze"><math>\displaystyle abbaaa \in \{aa, ab, ba\}^*</math></rightoption>
 </quiz>
@@ Linia 38: / Linia 37: @@
 Wskaż, które z poniższych odwzorowań są homomorfizmami:
-; a.
+<wrongoption reply="Źle"><math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(x)=3x</math></wrongoption>
-:  <math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(x)=3x</math>
-; b.
+<rightoption reply="Dobrze"><math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{R},+)</math>, <math>\displaystyle h(x)=3x</math></rightoption>
-:  <math>\displaystyle h: (\mathds{R},+) \rightarrow (\mathds{R},+)</math>, <math>\displaystyle h(x)=3x</math>
-; c.
+<wrongoption reply="Źle"><math>\displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)</math>,
-:  <math>\displaystyle h: (\mathds{R}, \cdot) \rightarrow (\mathds{R}, \cdot)</math>,
+<math>\displaystyle h(x)=3x</math></wrongoption>
-<math>\displaystyle h(x)=3x</math>
-; d.
+<rightoption reply="Dobrze"><math>\displaystyle h: \{a,b\}^* \rightarrow \{a,b\}^*</math>, <math>\displaystyle h(a)=a^2</math>,
-:  <math>\displaystyle h: \{a,b\}^* \rightarrow \{a,b\}^*</math>, <math>\displaystyle h(a)=a^2</math>,
+<math>\displaystyle h(b)=ab^2</math></rightoption>
-<math>\displaystyle h(b)=ab^2</math>
-; e.
+<rightoption reply="Dobrze"><math>\displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(a)=1</math>, <math>\displaystyle h(b)=1</math></rightoption>
-:  <math>\displaystyle h: \{a,b\}^* \rightarrow (\mathds{Z},+)</math>, <math>\displaystyle h(a)=1</math>,
-<math>\displaystyle h(b)=1</math>
 </quiz>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-b, d, e
-</div></div>
 <quiz>
@@ Linia 67: / Linia 56: @@
 stwierdzenia prawdziwe:
-; a.
+<wrongoption reply="Źle"><math>\displaystyle abc \in L_{gen}(RS, I)</math></wrongoption>
-:  <math>\displaystyle abc \in L_{gen}(RS, I)</math>
-; b.
+<rightoption reply="Dobrze"><math>\displaystyle ccb \in L_{gen}(RS, I)</math> </rightoption>
-:  <math>\displaystyle ccb \in L_{gen}(RS, I)</math>
-; c.
+<rightoption reply="Dobrze"><math>\displaystyle bb \in L_{gen}(RS, I)</math></rightoption>
-:  <math>\displaystyle bb \in L_{gen}(RS, I)</math>
-; d.
+<wrongoption reply="Źle"><math>\displaystyle aab \in L_{gen}(RS, I)</math></wrongoption>
-:  <math>\displaystyle aab \in L_{gen}(RS, I)</math>
-; e.
+<rightoption reply="Dobrze"><math>\displaystyle aa \in L_{gen}(RS, I)</math></rightoption>
-:  <math>\displaystyle aa \in L_{gen}(RS, I)</math>
 </quiz>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-b, c, e
-</div></div>
 <quiz>
@@ Linia 95: / Linia 75: @@
 język:
-; a.
+<rightoption reply="Dobrze"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k</math>, <math>\displaystyle \sharp_bw = 2l</math>,
-:  <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = 2k</math>, <math>\displaystyle \sharp_bw = 2l</math>,
+<math>\displaystyle k,l >0\}</math></rightoption>
-<math>\displaystyle k,l >0\}</math>
-; b.
+<wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 0 (mod 2)\}</math></wrongoption>
-:  <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 0 (mod 2)\}</math>
-; c.
+<wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw = 2k, k \geq
-:  <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw = \sharp_bw = 2k, k \geq
+\}</math></wrongoption>
-\}</math>
-; d.
+<wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 1 (mod 2)\}</math></wrongoption>
-:  <math>\displaystyle \{w \in \{a,b\}^*:\ \sharp_aw - \sharp_bw = 1 (mod 2)\}</math>
-; e.
+<wrongoption reply="Źle"><math>\displaystyle \{w \in \{a,b\}^*: \sharp_aw = 4k</math>, <math>\displaystyle \sharp_bw = 4l</math>, <math>\displaystyle k,
-:  <math>\displaystyle \{w \in \{a,b\}^*: \sharp_aw = 4k</math>, <math>\displaystyle \sharp_bw = 4l</math>, <math>\displaystyle k,
+l \geq 0\}</math></wrongoption>
-l \geq 0\}</math>
 </quiz>
-<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-a
-</div></div>
 <quiz>

Test GR: Różnice pomiędzy wersjami

Wersja z 11:33, 14 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia