IB102 – úkol 6, příklad 1 – řešení Odevzdání: 27. 10. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Sestrojte bezkontextovou gramatiku pro jazyk reprezentující sčítání cen
jablek a hrušek. Skupinu n jablek (nebo hrušek) zadáme jako n po sobě jdoucích symbolů
j (či symbolů h pro hrušku). Tedy například 3 jablka budou v našem jazyce vyjádřena jako
jjj, 2 hrušky jako hh. Ovoce sčítáme tak, že uvedeme libovolné jednodruhové skupiny
ovoce oddělené znakem „+“, za posledním ovocem je znak „=“ a následuje souhrnná
cena ovoce. Cena jablka je jedna koruna, hruška stojí koruny dvě. Cenu kódujeme jako
příslušný počet korun, tj. kkk = 3 koruny. Příklady slov z našeho jazyka:
• j = k
• jjj + h = kkkkk
• jj + hhh + j + h + j = kkkkkkkkkkkk
Speciálně je třeba dbát na to, že:
• Mezi dvěma skupinami stejného ovoce se nemůže objevit + (tedy například j + j =
kk nepatří do našeho jazyka).
• Na každé straně + musí být skupina ovoce (například jj+ = kk nepatří do jazyka,
+jj = kk nepatří do jazyka).
• Skupiny ovoce nesmí být prázdné, tedy například samotné = nepatří do našeho
jazyka, jj + +h = kkkk nepatří do jazyka.
Před sestavením gramatiky je třeba si uvědomit, jak budou slova generována. Správným
postupem může být postupné generování ovoce zleva a zároveň přidávaní korun zprava,
až dojdeme ke znaku =. Výsledná gramatika může vypadat například následovně:
G = ({S, J, H}, {j, h, k, +, =}, P, S)
P = {S → J | H,
J → jJk | j + Hk | j = k,
H → hHkk | h + Jkk | h = kk}
Přepisovací pravidla neterminálu S rozhodují, zdali slovo bude začínat znakem j, nebo h.
Pomocí neterminálů J a H pak generujeme skupiny ovoce. Buď rozšiřujeme danou skupinu
ovoce o nový kus, tedy přidáme ovoce na začátek a koruny na konec (pro neterminál J
platí, že se přepíše na jJk, pro neterminál H obdobně), nebo se rozhodneme skupinu
ovoce ukončit. Ukončení může nastat dvěma způsoby, buď je skupina ukončená znakem
+ (J se přepíše na j + Hk), pak musí následovat skupina druhého druhu ovoce, nebo se
ukončuje znakem =, tedy se celé slovo uzavře (J se přepíše na j = k).