Untitled

1 Wykonaj zadanie 1 i dowolne trzy
1. Wybieraj właściwą alternatywę.
(1 x 5 5 punktów)
(i) Wyrażenie regularne dla zestawu ciągów (01, 10} to
(a) (01) (10) (b) (01) 01 +10
(ii) Znajdź wyrażenie regularne reprezentujące zbiór ciągów w postaci amb c
gdzie m, n, p 21
(a) aa bb cc
pozostałych
abe
(c) (abc)*
(iii) Zbiór wszystkich ciągów nad {a,b) o parzystej długości jest reprezen-
towany przez wyrażenie regularne
(a)(aa+bb)*
(iv) W maszynie Turinga
(b) (a + b)(a + b)*
(c) (aa + ab + ba+bb)*
(a) r = E
(b) E c r
(v) Jeśli d(q, z) = (p. y. R) wtedy
(a) 12...-19... In 21x2...1-1ypti+1... In
(b) 12.-19...n12...i-1pxi+1...n
(c) 12...-19...nx12.-1Pti+1. n.
(c) Γ Ε Σ.
Każde poniższe pytanie zawiera 5 punktów.
2. Znajdź deterministyczny automat skończony równoważny M = ({90, 91, 92}, {a,b}, 8, 9o. (92})
gdzie & definiuje się następująco.
b
a
→ 90 {90,91} {92}
91
qo
91
*92
0 {90.91}
3. Skonstruuj automat stanu minimalnego równoważny automatowi którego
tabelę przejściową zdefiniowano w poniższej tabeli.
a b
→ 90 91 92
91 91 93
92 93 94
93 91 95
94 94 92
→95 90 91
4. Niech produkcje gramatyki G będą wynosić SaS Sbla/b. Sprawdź, czy
abab € L(G).
5. Skonstruktuj deterministyczny automat skończony, który akceptuje język,
który można wyrazić za pomocą wyrażenia regularnego a* + (ab+ a)*.