IB102 – úkol 12, příklad 1 – řešení Odevzdání: 17. 12. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Uvažme bezkontextovou gramatiku G = ({S, Á, B}, {a, l, n, ý, z}, P, S), kde
P = {S → aSa | nSl | ÁB,
Á → aS | Áa | z | .
B → lB | ýÁ | }.
Sestrojte analyzátor zdola nahoru a analyzujte slovo „analýza“.
Řešení
Analyzátor zdola nahoru pro jazyk L(G) sestrojený podle algoritmu je zásobníkový
automat M = ({q, r}, Σ = {a, l, n, ý, z}, {S, Á, B, ⊥, a, l, n, ý, z}, δ, q, ⊥, {r}), kde
δ(q, ε, aSa) = {(q, S)},
δ(q, ε, nSl) = {(q, S)},
δ(q, ε, ÁB) = {(q, S)},
δ(q, ε, aS) = {(q, Á)}
δ(q, ε, Áa) = {(q, Á)},
δ(q, ε, z) = {(q, Á)},
δ(q, ε, ε) = {(q, Á), (q, B)},
δ(q, ε, lB) = {(q, B)},
δ(q, ε, ýÁ) = {(q, B)},
∀x ∈ Σ δ(q, x, ε) = {(q, x)},
δ(q, ε, ⊥S) = {(r, ε)}.
Automat akceptuje koncovým stavem.
Analýza slova „analýza“:
(q, analýza, ⊥)
a
(q, nalýza, ⊥a)
n
(q, alýza, ⊥an)
ε
(q, alýza, ⊥anÁ)
a
(q, lýza, ⊥anÁa)
ε
(q, lýza, ⊥anÁ)
ε
(q, lýza, ⊥anÁB)
ε
(q, lýza, ⊥anS)
l
(q, ýza, ⊥anSl)
ε
(q, ýza, ⊥aS)
ε
(q, ýza, ⊥Á)
ý
(q, za, ⊥Áý)
z
(q, a, ⊥Áýz)
ε
(q, a, ⊥ÁýÁ)
a
(q, , ⊥ÁýÁa)
ε
(q, , ⊥ÁýÁ)
ε
(q, ε, ⊥ÁB)
ε
(q, ε, ⊥S)
ε
(r, ε, ε)