IA006 Automaty – závěrečná zkouška
0. termín – ukázková písemka
Příklad 1 [30 bodů]
Ukažte, že pro danou gramatiku G platí: (a) G je LALR(1) a (b) G není SLR(1).
Svá tvrzení podložte výpočty a zdůvodněte. G = ({S, A, B}, {a, b, c}, P, S), kde
P = { 1) S → AbB,
2) S → B,
3) A → cB,
4) A → a,
5) B → A}
(c) Pomocí Vašeho LALR(1) analyzátoru proveďte syntaktickou analýzu vstupního slova ca.
Příklad 2 [20 bodů]
(a) Definujte pojem bisimulace, bisimulační ekvivalence a aproximující bisimulace (∼n).
(b) Uvažme bisimulační hru na níže uvedeném přechodovém systému s počáteční konfigurací (A, F). Rozhodněte,
který hráč má pro tuto dvojici vítěznou strategii a ukažte nejdelší možnou partii obou hráčů z této
konfigurace.
G
b

c
A
a // B
b
OO
c //
c

D
b
oo
a // F
a

C
a
__
b // E
b
II
c
OO
Příklad 3 [20 bodů]
(a) Nechť Σ je lib. abeceda. Uveďte, jak je definována formule ϕ v logice MSO(Σ)
a jak je sentencí ϕ ∈ MSO(Σ) definován jazyk L(ϕ).
(b) Nechť Σ = {a, b}. Uveďte formuli ϕ ∈ MSO(Σ) takovou, že platí L(ϕ) = {aa}∗
.
(c) Nechť Σ = {a, b, c} a ϕ = ∀x Qa(x) ⇒ ∃y(x < y ∧ Qb(y)) je formule MSO(Σ).
Uveďte regulární výraz r nad Σ popisující jazyk L(ϕ).
1
Příklad 4 [30 bodů]
Buď dán jazyk L = {α ∈ {a, b, c, d}ω
| {a, b} inf (α) ∧ d ∈ inf (α)}.
(a) Sestrojte deterministický Mullerův automat M, který rozpoznává jazyk L.
(b) pro L sestrojte deterministický Büchiho automat D. Pokud takový automat neexistuje, dokažte či alespoň
zdůvodněte proč a sestrojte pro L nedeterministický Büchiho automat N.
2