IB102 – úkol 11, příklad 1 – řešení Odevzdání: 10. 12. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
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).
Řešení: Hledaný automat je vlastně automat rozpoznávající jazyk
L = {w ∈ {m, v, p}∗
| #m(u) + #v(u) ≥ #p(u), pro každý prefix u slova w}
a můžeme zkonstruovat například následovně. Idea konstrukce bude taková, že použijeme
zásobník jakožto počitadlo energie z párků, kterou lze použít na paření. Na zásobníku udržujeme
přesně tolik znaků E, kolik energie informatik zrovna má. Má-li informatik 0 energie,
na zásobníku nám zůstane jen symbol Z značící dno. Akceptujeme kdykoliv, když vidíme na
vrcholu E nebo Z. Vidíme-li Z, informatik může jen jíst, vidíme-li E, informatik může buď
jíst nebo pařit.
A = ({q, qf }, {p, v, m}, {E, Z}, δ, q, Z, {qf }), kde
δ(q, ε, Z) = {(qf , ε)} δ(q, ε, E) = {(qf , ε}
δ(q, m, Z) = {(q, EZ)} δ(q, m, E) = {(q, EE)}
δ(q, v, Z) = {(q, EEZ} δ(q, v, E) = {(q, EEE)}
δ(q, p, E) = {(q, ε)}
Automat akceptuje koncovým stavem.