IA006 Automaty – závěrečná zkouška
1. termín – 28. 1. 2021 14:00–16:30
Příklad 1 [30 bodů]
Je dána gramatika G = (N, Σ, P, S), kde N = {S, A, B}, Σ = {a, b, c} a
P = { 1. S → Aa,
2. S → cAc,
3. S → Bb,
4. A → bB,
5. B → ba,
6. B → a }.
(a) Pro G zkonstruujte LR(1) analyzátor.
(b) Rozhodněte, zda je G LALR(1) gramatikou. Svoje rozhodnutí zdůvodněte.
(c) Určete množinu {w ∈ Σ∗
| I(w) = ∅}. (Popište ji pomocí jazyků nad Σ a standardních
operací nad jazyky, nebo pomocí regulárního výrazu nad Σ.)
(d) Rozhodněte, zda L(G) je LL(1) jazyk, tedy zda existuje LL(1) gramatika, která ho generuje.
Svoji odpoveď dokažte nebo alespoň zdůvodněte.
Příklad 2 [20 bodů]
(a) Nalezněte konečněstavový přechodový systém s množinou stavů Q takový, že ∼2 = ∼3, ale
∼3 = ∼4.
(b) Popište, jak vypadají relace aproximující bisimulace (∼i pro i ∈ N0) na množině Q vašeho
přechodového systému.
(c) Najděte nekonečněstavový přechodový systém s množinou stavů S, stav s ∈ S a stav q ∈ Q
takové, že q a s jsou bisimulačně ekvivalentní.
Zadání zkoušky pokračuje na další straně.
1
Příklad 3 [25 bodů]
(a) Nechť Σ = {a, b, c}. Uveďte nějaký regulární výraz pro jazyk určený následující MSO(Σ)-
formulí:
∀x∀y (Qa(x) ∧ Qb(y)) ∨ (Qb(x) ∧ Qc(y)) → x < y
(b) Nechť Σ = {a, b}. Uveďte nějakou MSO(Σ)-formuli, která určuje jazyk zadaný regulárním
výrazem a∗
· b∗
· a∗
.
(c) Nechť Σ = {a, b}. Uveďte nějakou MSO(Σ)-formuli, která určuje jazyk zadaný regulárním
výrazem a∗
· b∗
· a∗
· b∗
· a∗
.
(d) Nechť Σ = {a, b}. Uveďte nějakou MSO(Σ)-formuli, která určuje jazyk zadaný regulárním
výrazem (abab)∗
.
Příklad 4 [25 bodů]
Nad abecedou Σ = {a, b, c, d} uvažme jazyk L = {α ∈ Σω
| c ∈ inf(α) ∧ |inf(α)| ≤ 2}.
(a) Sestrojte deterministický Mullerův automat (DMA), který akceptuje L.
(b) Sestrojte nedeterministický Büchiho automat (NBA), který akceptuje L.
(c) Kolik nejméně akceptujících stavů může mít automat z (b)? (Tedy přesněji řečeno: určete
nejmenší n ∈ N, pro něž existuje NBA, který akceptuje L a který má právě n akceptujících
stavů.) Dokažte správnost své odpovědi.
2