IB102 – úkol 8, příklad 3 – řešení Odevzdání: 24. 11. 2014
Vypracoval(a): UČO:
Skupina:
3. [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 shora dolů, 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}, Σ, N ∪ Σ, δ, q, S, ∅), kde
δ(q, ε, S) = {(q, aUm), (q, XSY )}
δ(q, ε, X) = {(q, Xa), (q, ε)}
δ(q, ε, Y ) = {(q, Xa), (q, Y t)}
δ(q, ε, U) = {(q, uU), (q, Uo), (q, t)}
∀c ∈ Σ δ(q, c, c) = {(q, ε)}
Automat akceptuje prázdným zásobníkem.
IB102 – úkol 8, příklad 3 – řešení Odevzdání: 24. 11. 2014
Vypracoval(a): UČO:
Skupina:
Analýza slova „automat“:
q, automat, S
ε
q, automat, XSY (2)
ε
q, automat, SY (4)
ε
q, automat, aUmY (1)
a
q, utomat, UmY
ε
q, utomat, uUmY (7)
u
q, tomat, UmY
ε
q, tomat, UomY (8)
ε
q, tomat, tomY (9)
t
q, omat, omY
o
q, mat, mY
m
q, at, Y
ε
q, at, Y t (6)
ε
q, at, Xat (5)
ε
q, at, at (4)
a
q, t, t
t
q, ε, ε
Tedy automat slovo akceptuje.
Použitá pravidla: 2, 4, 1, 7, 8, 9, 6, 5, 4.