IB005 úkol 8, příklad 1 Odevzdání: 19. 4. 2022 12:00
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. [0,5 bodu] Blíží se Velikonoce a informatik se rozhodl, že své blízké obdaruje velikonočními
vejci. Aby tak mohl učinit, musí vejce nejdříve koupit. Může se však také rozhodnout, že místo toho,
aby koupená vejce někomu daroval, sám je sní. Nicméně protože je informatik štědrý, rozhodl se, že
alespoň jedno koupené vejce někomu daruje.
Informatik tedy může velikonoční vejce: koupit (k), sníst (s) a darovat (d).
Dále musí platit:
• S velikonočním vejcem se může provádět cokoli dalšího až potom, co jej informatik koupí.
• Informatik se může rozhodnout, jestli vejce sní, nebo daruje. Maximálně se však toto rozhodnutí
týká jen tolika vajec, kolik jich má aktuálně koupených.
• Alespoň jedno vejce musí darovat, ale nemusí to nutně být první akce, kterou s vejci provede
– může sníst libovolné množství koupených vajec předtím, než se rozhodne nějaké darovat.
• Informatik musí spotřebovat všechna zakoupená vejce, tedy po Velikonocích mu žádné nezůstanou
doma.
Mějme tedy jazyk L nad abecedou Σ = {d, k, s}, který popisuje všechny možné sekvence akcí,
které může informatik s vejci dělat. Slova tohoto jazyka jsou tedy sekvence akcí, které splňují výše
popsané podmínky, kde vlevo je ta nejstarší akce a vpravo ta nejnovější akce.
Příklady slov patřících do jazyka L:
• kd
• kskd
• kdks
• kksd
• kkds
• kkddks
• kkkssd
• kksskd
• kkkssksd
Příklady slov nepatřících do jazyka L:
• ε
• ksd
• dks
• ksk
• ksdk
• kkdsk
Vaším úkolem je sestrojit bezkontextovou gramatiku, která generuje jazyk L. (Gramatika může, ale
nemusí obsahovat epsilon pravidla.)
Tento úkol je automaticky vyhodnocován podobně jako některé úkoly na regulární jazyky. Úkol se
odevzdává v ISu přes odpovědník „DÚ odevzdávání: úkol 08, příklad 1,“ v něm však nenajdete žádné
další informace k tomuto úkolu, doporučujeme jej tedy otevírat až po vyřešení úkolu.
Formát zápisu řešení je obdobný jako u odpovědníků na konstrukci regulárních gramatik, zapisujete
však samozřejmě gramatiku bezkontextovou. I tento formát je popsán na webu vyhodnocovací
služby – https://fja.fi.muni.cz/reg/userref. Syntaktické korektnosti prosím věnujte zvýšenou
pozornost, u bezkontextových gramatik bohužel nemáme k dispozici kontrolu syntaxe.
Případné dotazy k formalismu zápisu prosím směřujte do diskusního fóra.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.