IB102 úkol 8, příklad 1 Odevzdání: 20. 11. 2017
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. [2 body] Informatik se živí párky. Když sní malý párek, získá energii na hodinu paření. Když sní
velký párek, získá energii na dvě hodiny paření. Předpokládejme, že do informatika se vleze libovolné
množství párků. Informatik nikdy nesmí hrát více hodin, než na kolik se dopředu najedl. Povolené
sekvence akcí informatika jsou tedy jen ty, ve kterých nikdy nepaří déle než na kolik má energie z
párků.
Jazyk L nad abecedou {m, p, v} je množina všech povolených sekvencí akcí informatika, kde m
znamená akci „informatik snědl malý párek“, v znamená akci „informatik snědl velký párek“ a p
znamená akci „informatik hodinu pařil“. Například slova ε, mp, mmmvvvmmm, mmp, mvppmpp,
mpvpp nebo vpmp patří do jazyka L, zatímco slova pmm, mpp, vmpmppppm nikoliv.
Sestrojte bezkontextovou gramatiku pro jazyk L. Stručně, neformálně zdůvodněte, proč vaše gramatika
generuje právě jazyk L.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.