IB102 – úkol 6, příklad 1 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.