IA006 Automaty – závěrečná zkouška
2. termín – 4. 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 → cAa,
2. S → cB,
3. S → AbbA,
4. A → a,
5. B → abb }.
(a) Pro G zkonstruujte LR(1) analyzátor. Rozhodněte, zda je G LR(1) gramatikou.
(b) Najděte nejmenší k takové, že G je SLR(k) gramatikou. Dokažte správnost své odpovědi.
(c) Nalezněte gramatiku G1 takovou, že G1 je LR(1) gramatika, ale LALR(1) analyzátor pro G1
obsahuje konflikt redukce–redukce. Pokud taková neexistuje, dokažte to.
(d) Nalezněte gramatiku G2 takovou, že G2 je LR(1) gramatika, ale LALR(1) analyzátor pro G2
obsahuje konflikt čtení–redukce. Pokud taková neexistuje, dokažte to.
Příklad 2 [20 bodů]
Rozhodněte, zda platí následující implikace. Svá rozhodnutí dokažte.
(a) L je LR(0) jazyk =⇒ co−L je deterministický bezkontextový jazyk
(b) L je deterministický bezkontextový jazyk =⇒ co−L je LR(0) jazyk
Zadání zkoušky pokračuje na další straně.
1
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(first(x) ∧ Qa(x))
∀x(first(x) → Qa(x))
∃x(first(x) ∧ Qa(x))
∃x(first(x) → Qa(x))
(b) Uveďte nějakou MSO(Σ)-formuli ϕ s volnou prvořádovou proměnnou x takovou, že (w, I) |=
ϕ platí právě tehdy, když I(x) je pozice prvního znaku a ve slově w ∈ Σ∗
.
(c) Uveďte nějakou MSO(Σ)-formuli ϕ s volnou druhořádovou proměnnou X takovou, že (w, I) |=
ϕ platí právě tehdy, když I(X) obsahuje právě pozice prvního, třetího, pátého. . . znaku a ve
slově w ∈ Σ∗
.
Pro ilustraci uvádíme příklad čtyř slov, příslušné hodnoty pro x, při nichž má být splněná formule
z (b) (všimněte si, že taková vždy existuje nejvýš jedna), a příslušné hodnoty pro X, při nichž má
být splněná formule z (c) (všimněte si, že taková vždy existuje právě jedna):
w I(x) I(X)
a9
1 {1, 3, 5, 7, 9}
bbaa 3 {3}
(ba)8
2 {2, 6, 10, 14}
b — ∅
Příklad 4 [25 bodů]
Nad abecedou Σ = {a, b, c} uvažme jazyk L = {α ∈ Σω
| a ∈ inf(α) ∧ (b ∈ inf(α) ∨ c ∈ inf(α))}.
(a) Sestrojte deterministický Mullerův automat (DMA), který akceptuje L.
(b) Sestrojte deterministický Streettův automat (DSA), který akceptuje L.
(c) Sestrojte nedeterministický Büchiho automat (NBA), který akceptuje L.
(d) Existuje deterministický Büchiho automat (DBA), který akceptuje L? Správnost své odpovědi
dokažte.
2