IB102 - úkol 10 - řešení Odevzdání: 12.12. 2011 Vypracoval: James Bond UČO: 007 Skupina: MI6 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ě! IB 102 - úkol 10 - řešení Odevzdání: 12.12. 2011 Vypracoval: James Bond Skupina: MI6 UCO: 007 Řešení (a): Syntaktický analyzátor metodou shora dolů vypadá takto: Atd = ({q},Ľ,ĽUN,ô,q,V,®),kde ô(q,e,V) ô(q,e,W) ó(q, e, Podmět) ó(q, e, Predmet) ô(q, e, Kdo) ô(q, e, Koho) ô(q,e, Jakou) ô(q, e, Sloveso) {(g, Podmet Sloveso Předmět)} {(g,, která Sloveso Předmět)} {(g, Kdo), (g, Kdo W,)} {(g, Koho), (g, Koho W), (g, Jakou Předmět)} {(g, žena), (g, růže), (g, píseň), (g, kost)} {(q, ženu), (g, růži), (g, píseň), (g, kost)} {(g, krásnou), (g, tvrdou), (g, ostrou)} {(g, zpívá), (g, vidí), (g, vaří)} ô(q, žena, žena ô(q, píseň, píseň ô(q, ženu, ženu ô(q, krásnou, krásnou ô(q, ostrou, ostrou ô(q, vidí, vidí {(q,e,e)} 5(q, která, která) = {(q,e,e)} {(q,e,e)} 6(g, růže, růže) = {(g,e,e)} {(q,e,e)} 6(g, kost, kost) = {(g,e,e)} {(q,e,e)} 6(g, růži, růži) = {(g,e,e)} {(g, £,£■)} tvrdou, tvrdou) = {(q, zpívá, zpívá) = {(g,e,e)} 5(g, vaří, vaří) = Syntaktickou analýzou slova žena , která vaří tvrdou kost , zpívá ostrou píseň je pak následující výpočet: žena , která vaří tvrdou kost žena , která vaří tvrdou kost žena , která vaří tvrdou kost žena , která vaří tvrdou kost -(g,, která vaří tvrdou kost , zpívá ostrou píseň, W, Sloveso Předmět) \—(q,, která vaří tvrdou kost , zpívá ostrou píseň,, která Sloveso Předmět , Sloveso Předmět) p"-(g, která vaří tvrdou kost , zpívá ostrou píseň, která Sloveso Předmět , Sloveso Předmět) .která .tvrdou .kost q, vaří tvrdou kost , zpívá ostrou píseň, Sloveso Předmět , Sloveso Předmět) g, vaří tvrdou kost , zpívá ostrou píseň, vaří Předmět , Sloveso Předmět) q, tvrdou kost , zpívá ostrou píseň, Předmět , Sloveso Předmět) (/.tvrdou kost , zpívá ostrou píseň. Jakou Předmět , Sloveso Předmět) //.tvrdou kost , zpívá ostrou píseň,tvrdou Předmět , Sloveso Předmět) (/. kost , zpívá ostrou píseň, Předmět , Sloveso Předmět) (/, kost , zpívá ostrou píseň, Koho , Sloveso Předmět) (/, kost , zpívá ostrou píseň, kost , Sloveso Předmět) q,, zpívá ostrou píseň,, Sloveso Předmět) q, zpívá ostrou píseň, Sloveso Předmět) q, zpívá ostrou píseň, zpívá Předmět) q, ostrou píseň, Předmět) q, ostrou píseň, Jakou Předmět) (7, ostrou píseň, ostrou Předmět) q, píseň, Předmět) q, píseň, Koho) g, píseň, píseň) Slovo žena , která vaří tvrdou kost , zpívá ostrou píseň je akceptováno, je tedy možné jej odvodit v zadané gramatice. | 2. zpiva .ostrou píseň IB102 - úkol 10 - řešení Odevzdání: 12.12. 2011 Vypracoval: James Bond UČO: 007 Skupina: MI6 Řešení (b): Syntaktický analyzátor metodou zdola nahoru vypadá takto: Au = ({q, r}, E, E U N U {_L}, ô, q, _L, {r}), kde ô(q,e, Podmet Sloveso Predmet) = { [q,v)} 5(q, e, žena) = { ;g,Kdo)} 5(q,e,, která Sloveso Predmet) = { <5T<7, e, růže) = { ;g,Kdo)} ô(q,e, Kdo) = { [q, Podmet)} 5(q, e, ženu) = { [q, Koho)} ô(q,e,Kdo W,) = { [q, Podmet)} <5T<7, e, růži) = { [q, Koho)} ô(q, e, Koho) = { [q, Predmet)} 5(q, e, píseň) = { [q, Kdo), (g, Koho)} ô(q,e, Koho W) = { [q, Predmet)} <5T<7, e, kost) = { [q, Kdo), (g, Koho)} ô(q,e, Jakou Predmet) = { [q, Predmet)} S(q, e, krásnou) = { [q,Jakou)} čfg, e, tvrdou) = { [q,Jakou)} 5{q, e, ostrou) = { [q,Jakou)} ô(q, e, zpívá) = { [q, Sloveso)} <5T<7, e, vidí) = { [q, Sloveso)} <5T<7, e, vaří) = { [q, Sloveso)} 5(q,s,±V) = { ô(q,ve) = { [q,?)} 5(q, která, e) = { 'g, která)} ô(q, žena, e) = { 'q, žena)} 5(q, růže, e) = { 'g, růže)} ô(q, ženu, e) = { 'q, ženu)} 5(q, růži, e) = { ;g,růži)} ô(q, píseň, e) = { [q, píseň)} 5(q, kost, e) = { 'q, kost)} 5{q, krásnou, e) = { ŕ/, krásnou)} 5(q, ostrou, e) = { '(/, ostrou)} ô(q, tvrdou, e) = { 'q, tvrdou)} 5(q, zpívá, e) = { [q, zpívá)} ô(q, vidí, e) = { ^9, vidí)} 5(q, vaří, e) = { 'g, vaří)} Syntaktickou analýzou slova růže , která zpívá krásnou píseň , zpívá krásnou píseň je pak následující výpočet: (g, růže , která zpívá krásnou píseň , zpívá krásnou píseň, _L) |-(g,, která zpívá krásnou píseň , zpívá krásnou píseň, _l_růže) \—(q,, která zpívá krásnou píseň , zpívá krásnou píseň, _LKdo) která zpívá krásnou píseň , zpívá krásnou píseň, _LKdo ,) (g, zpívá krásnou píseň , zpívá krásnou píseň, _LKdo , která) (q, krásnou píseň , zpívá krásnou píseň, _LKdo , která zpívá) \—(q, krásnou píseň , zpívá krásnou píseň, _LKdo , která Sloveso) .krásnou pisen zprva .krásnou .pisen q, píseň , zpívá krásnou píseň, _LKdo , která Sloveso krásnou) q, píseň , zpívá krásnou píseň, _LKdo , která Sloveso Jakou) q,, zpívá krásnou píseň, _LKdo , která Sloveso Jakou píseň) q,, zpívá krásnou píseň, _LKdo , která Sloveso Jakou Koho) q,, zpívá krásnou píseň, _LKdo , která Sloveso Jakou Předmět) q,, zpívá krásnou píseň, _LKdo , která Sloveso Předmět) q,, zpívá krásnou píseň, _LKdo W) q, zpívá krásnou píseň, _LKdo W ,) q, zpívá krásnou píseň, _LPodmět) q, krásnou píseň, _LPodmět zpívá) ť/, krásnou píseň, _LPodmět Sloveso) q, píseň, _LPodmět Sloveso krásnou) q, píseň, _LPodmět Sloveso Jakou) q, £,_LPodmět Sloveso Jakou píseň) q, £,_LPodmět Sloveso Jakou Koho) q,£,_LPodmět Sloveso Jakou Předmět) q, £,_LPodmět Sloveso Předmět) q,e,±V) Slovo růže , která zpívá krásnou píseň , zpívá krásnou píseň je akceptováno, je tedy možné jej odvodit v zadané gramatice. IB102 - úkol 10 - řešení Odevzdání: 12.12. 2011 Vypracoval: James Bond UČO: 007 Skupina: MI6 Řešení (c): CYK tabulka pro slovo žena vidí ženu , která vaří růži vypadá takto: {V} 0 {X} 0 0 {Předmět} 0 0 0 {W} {V} 0 0 0 {Z} 0 m 0 0 0 {X} {Kdo, Podmět} {Sloveso} {Koho, Předmět} {Y} {K} {Sloveso} {Koho, Předmět} žena vidí ženu 5 která vaří růži Vidíme, že počáteční neterminál V je obsažen v T17 (nejvyšší pole tabulky). Slovo žena vidí ženu , která vaří růži je tedy možné odvodit v zadané gramatice. IB 102 - úkol 10 - řešení Odevzdání: 12.12. 2011 Vypracoval: James Bond UČO: 007 Skupina: MI6 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í. Řešení: Idea konstrukce bude taková, že použijeme zásobník jakožto počitadlo dosud nezaplacené částky. Hledaný automat pak můžeme zkonstruovat například takto: A = ({