IB102 úkol 11, příklad 1 Odevzdání: 9. 12. 2019
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] V této úloze budeme vytvářet denní plán informatika. Klasický informatik (pro zjednodušení)
dělá následující činnosti: pracuje (p), pije kávu (k), odpočívá (o) nebo jí jídlo (j).
Tento denní plán rozdělíme do vícero bloků činností (práce a odpočinku) oddělených jídlem nebo
kávou. Na denní plán informatika máme následující požadavky:
• Musí jíst alespoň jednou denně.
• V každém bloku činností může být maximálně dvakrát tolik jednotek práce co odpočinku (tedy
pro každý blok b platí, že #p(b) ≤ 2 · #o(b)).
• Na začátku a na konci denního plánu (před prvním a za posledním blokem činnosti) může, ale
nemusí být jídlo nebo káva.
Nechť L je jazyk všech správně utvořených denních plánů informatika nad abecedou Σ = {p, k, o, j}.
Příklady slov patřících do jazyka: j, oj, joop, okoj, oojpop, pojkp5o3jj, ojoopkjpook.
Příklady slov nepatřících do jazyka: o, p, jp, jpppo, ppjoo, ok, ojpokpk.
Sestrojte (obyčejný, nikoli rozšířený) nedeterministický zásobníkový automat akceptující jazyk L.
Jasně uveďte, jakým způsobem váš automat akceptuje.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.