IB102 úkol 11, příklad 3 Odevzdání: 10. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
3. [2 body] (Příklad odevzdávejte do skříňky 2 nebo do příslušné odevzdávárny.)
Uvažte bezkontextovou gramatiku G:
G = ({S, M, H}, {−, d, u, (, )}, P, S)
P = {(1) S → M,
(2) S → −H,
(3) S → ε,
(4) M → (−H),
(5) M → (M − M),
(6) M → d,
(7) M → u,
(8) H → M,
(9) H → (−H),
(10) H → d}.
Sestrojte analyzátor zdola nahoru, analyzujte slovo „−((−(−d)) − u)“ 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 rozšířený zásobníkový automat M = ({q, r}, Σ, N ∪ Σ ∪ {⊥}, δ, q, ⊥, {r}), kde
N = {S, M, H}
Σ = {−, d, u, (, )}
δ(q, ε, M) = {(q, S), (q, H)}
δ(q, ε, −H) = {(q, S)}
δ(q, ε, ε) = {(q, S)}
δ(q, ε, (−H)) = {(q, M), (q, H)}
δ(q, ε, (M − M)) = {(q, M)}
δ(q, ε, d) = {(q, M), (q, H)}
δ(q, ε, u) = {(q, M)}
∀a ∈ Σ δ(q, a, ε) = {(q, a)}
δ(q, ε, ⊥S) = {(r, ε)}
Automat akceptuje koncovým stavem.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 11, příklad 3 Odevzdání: 10. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Analýza slova „−((−(−d)) − u)“:
q, − ((−(−d)) − u) , ⊥
−
q, ((−(−d)) − u) , ⊥ −
(
q, (−(−d)) − u) , ⊥ − (
(
q, − (−d)) − u) , ⊥ − ((
−
q, (−d)) − u) , ⊥ − ((−
(
q, − d)) − u) , ⊥ − ((−(
−
q, d)) − u) , ⊥ − ((−(−
d
q, )) − u) , ⊥ − ((−(−d
ε
(10) q, )) − u) , ⊥ − ((−(−H
)
q, ) − u) , ⊥ − ((−(−H)
ε
(9) q, ) − u) , ⊥ − ((−H
)
q, − u) , ⊥ − ((−H)
ε
(4) q, − u), ⊥ − (M
−
q, u), ⊥ − (M −
u
q, ), ⊥ − (M − u
ε
(7) q, ), ⊥ − (M − M
)
q, ε, ⊥ − (M − M)
ε
(5) q, ε, ⊥ − M
ε
(8) q, ε, ⊥ − H
ε
(2) q, ε, ⊥S
ε
r, ε, ε
Přečetli jsme slovo a skončili v akceptujícím stavu, tedy automat slovo akceptuje.
Použitá pravidla: 10, 9, 4, 7, 5, 8, 2.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.