IB005 úkol 8, příklad 1 Odevzdání: 25. 4. 2021 23:59
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] Systém na registraci k očkování je v nespolehlivé databázi, která se ale občas zálohuje.
Chceme spočítat počet registrovaných, kteří se neztratili pádem databáze.
Budeme tedy popisovat jazyk, jehož slova jsou tvaru „sekvence akcí“ ∼ „počet registrovaných“,
přičemž v sekvenci akcí jsou nejstarší akce nejvíce vlevo a nejnovější akce nejvíce vpravo. Počet
registrovaných počítáme unárně (tedy počet neztracených registrací chceme vyjádřit počtem znaků
1 – jedna 1 za každou neztracenu registraci).
S databází se mohou dít tyto akce:
• r – registrace k očkování
• b – záloha databáze (backup)
• c – pád databáze = ztráta nezálohovaných dat (crash)
Započítávají se ti registrovaní, za nimiž není pád nepředcházený zálohou. Jinými slovy, počítáme
ty registrace, po kterých neproběhl žádný pád databáze, nebo které byly před nejbližším dalším
pádem zazálohované.
Formálněji, pokud sekvenci akcí rozdělíme na části oddělené zálohami, pak počet registrovaných
je dán součtem registrací v každé sekvenci za posledním pádem databáze v této sekvenci (nebo v
celé sekvenci pokud k pádu nedošlo).
Mějme tedy jazyk L nad abecedou Σ = {r, b, c, ∼, 1}. Potom L obsahuje všechna slova tvaru {r, b, c}∗·
{∼} · {1}∗, v nichž počet 1 odpovídá počtu neztracených registrací po dané sekvenci akcí.
Příklady slov patřících do jazyka L:
• ∼
• r ∼ 1
• bcb ∼
• cbcrrr ∼ 111
• rrrrc ∼
• rrbcrbrrc ∼ 111
Příklady slov nepatřících do jazyka L:
• ∼∼
• rb1
• rb ∼
• ∼ 11
• 1 ∼ r
• rbrrcb ∼ 111
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.