IB102 – úkol 11, příklad 1 Odevzdání: 10. 12. 2012
Vypracoval(a): UČO:
Skupina:
2. [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 slovo , mmmvvvmmm, mmp,
mvppmpp, nebo vpmp patří do jazyka L, zatímco slova pmm, mpp, vmpmppppm nikoliv.
Sestrojte zásobníkový automat akceptující jazyk L. Jasně uveďte, jakým způsobem Váš
automat akceptuje (koncovým stavem, prázdným zásobníkem).