IB102 - úkol 10
Odevzdání: 12.12. 2011
Vypracoval (a): UČO: Skupina:
1. [6 bodů] Mějme následující gramatiku: G = (N, E, P, V), kde
N =   {V, W, Podmet, Predmet, Kdo, Koho, Jakou, Sloveso}, E =   {,, která, žena, růže, píseň, kost, ženu, růži, krásnou, tvrdou, ostrou, zpívá, vidí, vaří}
P = {
V	-ř	Podmět Sloveso Předmět
w	—ř	, která Sloveso Předmět
Podmet	—ř	Kdo | Kdo W,
Predmet	—ř	Koho  Koho W  Jakou Předmět
Kdo	—ř	žena  růže  píseň kost
Koho	—ř	ženu  růži  píseň kost
Jakou	—ř	krásnou  tvrdou ostrou
Sloveso	—ř	zpívá  vidí  vaří }.
(a) Pro gramatiku G sestrojte syntaktický analyzátor metodou shora dolů. Analyzujte slovo žena , která vaří tvrdou kost , zpívá ostrou píseň.
(b) Pro gramatiku G sestrojte syntaktický analyzátor metodou zdola nahoru. Analyzujte slovo růže , která zpívá krásnou píseň , zpívá krásnou píseň.
(c) Pomocí deterministické analýzy (CYK) analyzujte slovo žena vidí ženu , která vaří růži. Pro usnadnění práce je zde k dispozici gramatika převedená na CNF:
G' = (N U {X, Y, Z, U, K}, E, P', V), kde
P' = {
V		Podmět X	
w		YZ	
Podmet	—ř	žena  růže píseň	| kost | Kdo U
Předmět	—ř	ženu  růži píseň	kost   Koho W
Kdo	—ř	žena  růže píseň	kost
Koho	—ř	ženu  růži píseň	kost
Jakou	—ř	krásnou tvrdou	ostrou
Sloveso	—ř	zpívá  vidí vaří	
X	—ř	Sloveso Předmět	
Y	—ř		
Z	—ř	KX	
U	—ř	WY	
K	—ř	která |.	
Poznámka: Dobře si všimněte, jaká je množina terminálů a neterminálů gramatiky, zejména, že terminál je i znak , (čárka).
Odevzdávejte, prosím, každou část příkladu na zvláštním listě!
IB102 - úkol 10
Odevzdání: 12.12. 2011
Vypracoval (a): UČO: Skupina:
2. [2 body] Mějme následující jazyk nad abecedou {O, Q, ©, @, lOmin, 60min}: L = {xy\   x G {lOmm, 60min}+,í/ G {O, ©,©,©}*,
14 • #l0min(^) + 22 • #60min(^) < #o(ž/) + 2 • #.(*/) + 5 • #„(*/) + 10 • #©(?/)}
Sestrojte zásobníkový automat akceptující jazyk L. Jasně uveďte, jakým způsobem Váš automat akceptuje (koncovým stavem, prázdným zásobníkem).
Motivace: Cílem je sestrojit automat na jízdenky. Uživatel automatu nejdříve zvolí počet a typ jízdenek (pomocí dvou tlačítek lOmin a 60min), následně vhazuje mince O, ©, ©, ©. Automat vydá jízdenky (tj. akceptuje vstup), pokud je hodnota vhozených mincí větší nebo rovná hodnotě jízdenek (desetiminutová jízdenka stojí 14 korun, hodinová stojí 22). Automat nevrací.