IB102 – úkol 8, příklad 2 – řešení Odevzdání: 25. 11. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažme bezkontextovou gramatiku G = (N, Σ, P, S), kde
N = {S, X, T}
Σ = {x, t, f, [, ], ∧, ¬, ⇒}
P = {(1) S → ¬S,
(2) S → [S ∧ S],
(3) S → [S ⇒ S],
(4) S → x,
(5) S → xX,
(6) S → T,
(7) X → x,
(8) X → xX,
(9) T → t,
(10) T → f}.
Sestrojte analyzátor shora dolů, analyzujte slovo „[¬f ∧ xx]“ 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}, Σ, N ∪ Σ, δ, q, S, ∅), kde
δ(q, ε, S) = {(q, ¬S), (q, [S ∧ S]), (q, [S ⇒ S]), (q, x), (q, xX), (q, T)}
δ(q, ε, X) = {(q, x), (q, xX)}
δ(q, ε, T) = {(q, t), (q, f)}
∀a ∈ Σ δ(q, a, a) = {(q, ε)}
Automat akceptuje prázdným zásobníkem.
Analýza slova „[¬f ∧ xx]“:
q, [¬f ∧ xx], S
ε
q, [¬f ∧ xx], [S ∧ S]
[
q, ¬f ∧ xx], S ∧ S]
ε
q, ¬f ∧ xx], ¬S ∧ S]
¬
q, f ∧ xx], S ∧ S]
ε
q, f ∧ xx], T ∧ S]
ε
q, f ∧ xx], f ∧ S]
f
q, ∧ xx], ∧ S]
∧
q, xx], S]
ε
q, xx], xX]
x
q, x], X]
ε
q, x], x]
x
q, ], ]
]
q, ε, ε
Tedy automat slovo akceptuje.
Použitá pravidla: 2, 1, 6, 10, 5, 7.
1