IB005 úkol 11, příklad 1 Odevzdání: 9. 5. 2022 12:00
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.
1. [0,5 bodu] Uvažte následující bezkontextovou gramatiku G generující výrazy zjednodušeného
Systému F (Lambda kalkul druhého řádu):
G = ({M, X, T, A}, {x, a, ., :, [, ], λ, ∀, ⇒}, P, M),
P = {
(1) M → X, (4) X → xX, (6) T → a, (10) A → aA,
(2) M → [λX : T. M], (5) X → ε, (7) T → aA, (11) A → a
(3) M → [MM], (8) T → [T ⇒ T],
(9) T → [∀A. T],
}.
a) Uveďte analyzátor shora dolů a analyzujte pomocí něj slovo „[λx : [a ⇒ aa]. x]“.
b) Uveďte analyzátor zdola nahoru a analyzujte pomocí něj slovo „[[λx : a. x] x]“.
Zapište celý postup výpočtu analyzátoru (vizte definici 3.37 ze skript). K přechodům mezi stavy
výpočtu napište kromě čteného písmene také číslo pravidla gramatiky G, které jste v daném kroku
použili
čtené písmeno
číslo pravidla .
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.