IB102 – úkol 12, příklad 1 – řešení Odevzdání: 17. 12. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [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 shora dolů a analyzujte slovo „analýza“.
Řešení
Analyzátor shora dolů pro jazyk L(G) sestrojený podle algoritmu je zásobníkový automat
M = ({q}, Σ = {a, l, n, ý, z}, {S, Á, B} ∪ Σ, δ, q, S, ∅), kde
δ(q, ε, S) = {(q, aSa), (q, nSl), (q, ÁB)}
δ(q, ε, Á) = {(q, aS), (q, Áa), (q, z), (q, ε)}
δ(q, ε, B) = {(q, lB), (q, ýÁ), (q, ε)}
∀x ∈ Σ δ(q, x, x) = {(q, ε)}
Automat akceptuje prázdným zásobníkem.
Analýza slova „analýza“:
(q, analýza, S)
ε
(q, analýza, ÁB)
ε
(q, analýza, aSB)
a
(q, nalýza, SB)
ε
(q, nalýza, nSlB)
n
(q, alýza, SlB)
ε
(q, alýza, ÁBlB)
ε
(q, alýza, ÁaBlB)
ε
(q, alýza, aBlB)
a
(q, lýza, BlB)
ε
(q, lýza, lB)
l
(q, ýza, B)
ε
(q, ýza, ýÁ)
y
(q, za, Á)
ε
(q, za, Áa)
ε
(q, za, za)
z
(q, a, a)
a
(q, ε, ε)