IB102 – úkol 8, příklad 4 – řešení Odevzdání: 24. 11. 2014
Vypracoval(a): UČO:
Skupina:
4. [2 body] Uvažme bezkontextovou gramatiku G = (N, Σ, P, S), kde
N = {S, X, Y, U}
Σ = {a, m, o, t, u}
P = {(1) S → aUm,
(2) S → XSY,
(3) X → Xa,
(4) X → ε,
(5) Y → Xa,
(6) Y → Y t,
(7) U → uU,
(8) U → Uo,
(9) U → t, }.
Sestrojte analyzátor zdola nahoru, analyzujte slovo „automat“ a zapište čísla pravidel
gramatiky G v pořadí, ve kterém se při analýze tohoto slova použijí odpovídající přechody
analyzátoru.
Analyzátor je zásobníkový automat M = ({q, r}, Σ, N ∪ Σ ∪ {⊥}, δ, q, ⊥, {r}), kde
∀c ∈ Σ δ(q, c, ε) = {(q, c)}
δ(q, ε, aUm) = {(q, S)}
δ(q, ε, XSY ) = {(q, S)}
δ(q, ε, Xa) = {(q, X), (q, Y )}
δ(q, ε, ε) = {(q, X)}
δ(q, ε, Y t) = {(q, Y )}
δ(q, ε, uU) = {(q, U)}
δ(q, ε, Uo) = {(q, U)}
δ(q, ε, t) = {(q, U)}
δ(q, ε, ⊥S) = {(r, ε)}
Automat akceptuje koncovým stavem.
IB102 – úkol 8, příklad 4 – řešení Odevzdání: 24. 11. 2014
Vypracoval(a): UČO:
Skupina:
Analýza slova „automat“:
q, automat, ⊥
ε
q, automat, ⊥X (4)
a
q, utomat, ⊥Xa
u
q, tomat, ⊥Xau
t
q, omat, ⊥Xaut
ε
q, omat, ⊥XauU (9)
o
q, mat, ⊥XauUo
ε
q, mat, ⊥XauU (8)
ε
q, mat, ⊥XaU (7)
m
q, at, ⊥XaUm
ε
q, at, ⊥XS (1)
ε
q, at, ⊥XSX (4)
a
q, t, ⊥XSXa
ε
q, t, ⊥XSY (5)
t
q, ε, ⊥XSY t
ε
q, ε, ⊥XSY (6)
ε
q, ε, ⊥S (2)
ε
r, ε, ε
Tedy automat slovo akceptuje.
Použitá pravidla: 4, 9, 8, 7, 1, 4, 5, 6, 2.