IA006 Automaty – závěrečná zkouška
3. termín – 18. 2. 2021 14:00–16:30
Příklad 1 [30 bodů]
Je dána gramatika G = ({S, A, B}, {a, b, c}, P, S), kde
P = { 1. S → a,
2. S → AA,
3. S → BAb,
4. A → a,
5. B → ε,
6. B → cA }.
(a) Pro G zkonstruujte LL(2) analyzátor. Rozhodněte, zda je G LL(2) gramatikou.
(b) Pomocí vašeho analyzátoru analyzujte slovo caab.
(c) Rozhodněte, zda L(G) je LR(0) jazyk. Svoji odpověď dokažte.
(d) Rozhodněte, zda L(G) je LR(1) jazyk. Svoji odpověď dokažte.
Příklad 2 [20 bodů]
(a) Nalezněte šestistavový přechodový systém nad množinou akcí Act = {a} takový, že ∼ má tři
třídy ekvivalence.
(b) Nalezněte šestistavový přechodový systém nad množinou akcí Act = {a} takový, že ∼ má
čtyři třídy ekvivalence.
(c) Nalezněte nekonečněstavový přechodový systém nad množinou akcí Act = {a} takový, že ∼
má tři třídy ekvivalence.
Ve všech případech také explicitně uveďte, čemu jsou rovny bisimulační ekvivalence (relace ∼).
Zadání zkoušky pokračuje na další straně.
1
Definice. b-úsekem (konečného či nekonečného) slova w rozumíme libovolnou dvojici [i, j] takovou,
že na pozici i ve slově w je b a j je pozice nejbližšího následujícího znaku b. Délka b-úseku [i, j]
je j − i + 1. (Pro ilustraci: Slovo babbab obsahuje následující b-úseky: [1, 3] délky 3, [3, 4] délky 2 a
[4, 6] délky 3. Slovo aba nemá žádné b-úseky. Ve slově (aab)ω
jsou b-úseky právě dvojice [3n, 3n+3]
pro libovolné celé kladné n a všechny mají délku 4.)
Příklad 3 [25 bodů]
Nechť Σ = {a, b}.
(a) Pro každou z následujících MSO(Σ)-formulí uveďte jazyk jí určený:
∀x∀y(x = y)
∀x∃y(x = y)
∃x∀y(x = y)
∃x∃y(x = y)
(b) Sestrojte deterministický konečný automat (DFA) pro jazyk určený MSO(Σ)-formulí
∀y(y < x → Qa(y)).
(Všimněte si, že proměnná x je volná, tedy vstupní abecedou vašeho DFA bude Σ × {0, 1}.)
(c) Uveďte nějakou MSO(Σ)-formuli, která určuje jazyk
{w ∈ Σ∗
| všechny b-úseky ve slově w mají lichou délku}.
Příklad 4 [25 bodů]
Nad abecedou Σ = {a, b} uvažme jazyk
L = {α ∈ Σω
| α obsahuje nekonečně mnoho b-úseků liché délky}.
(a) Pokud existuje deterministický Büchiho automat (DBA), který akceptuje L, sestrojte jej.
V opačném případě sestrojte nedeterministický Büchiho automat (NBA), který akceptuje L,
a dokažte, že příslušný DBA neexistuje.
(b) Totéž proveďte pro jazyk co−L.
2