IB102 úkol 11, příklad 1 Odevzdání: 10. 12. 2018
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] Uvažme následující jazyk nad abecedou Σ = {a, b, ?}:
L = {u?vR
| u ∈ {a, b}∗
, v = zkrat(u)},
kde zkrat je funkce, která v daném slově nahradí každou maximální sekvenci všech bezprostředně
po sobě následujících znaků a jedním znakem a a každou maximální sekvenci všech bezprostředně po
sobě následujících znaků b jedním znakem b. Tedy například zkrat(aab) = ab, zkrat(baaaabba) =
baba, zkrat(aabbbbaaabbbabb) = ababab nebo zkrat(ε) = ε.
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.
Pro jednoduchost požadovaný automat označme A. Automat A se zřejmě bude skládat ze dvou
částí, protože bude muset umět rozlišit, kdy jsme už načetli ?.
V první části, tedy před přečtením ?, budeme pro některé a nebo b naplňovat zásobník odpovídajícími
zásobníkovými symboly A nebo B. A to právě tehdy, pokud narazíme na znak různý od
toho předešlého, nebo na první znak. To zaručí, že na zásobníku nebudou žádné sekvence A a B
délky více než 1.
Konkrétně to budeme rozlišovat tak, že po prvním znaku přejdeme z iniciálního stavu do odpovídajícího
stavu qA nebo qB podle toho, jestli jsme přidali na zásobník A nebo B. V qA nebudeme
pod a přidávat žádné A a pod b přidáme B a přejdeme do qB. Obdobně pro qB.
Přečtením prvního ? přejdeme do druhé části, ať jsme již načetli cokoli a stav zásobníku je
jakýkoliv. V této druhé části, tedy po přečtení ?, budou existovat přechody jenom pod a nebo b
a to jen tehdy, pokud bude na vrcholu zásobníku odpovídající zásobníkový symbol A nebo B, v
opačném případě se A zasekne. Každým přechodem přitom umažeme vrchol zásobníku, takto se
zaručí obrácené pořadí i funkce zkrat, na zásobníku totiž nejsou žádné sekvence stejných znaků.
Protože budeme chtít, aby slovo neobsahovalo nic za vR, budeme akceptovat prázdným zásobníkem:
prázdným zásobníkem podle definice A akceptuje jenom tehdy, pokud jsme již načetli všechny
znaky. Pokud tedy narazíme na vrchol Z, provedeme ε-přechod, který ho umaže.
Formálně, nechť A = ({q0, qA, qB, q1, q2}, Σ, {A, B, Z}, δ, q0, Z, ∅), kde
δ(q0, a, Z) = {(qA, AZ)}
δ(q0, b, Z) = {(qB, BZ)}
δ(qA, a, A) = {(qA, A)}
δ(qA, b, A) = {(qB, BA)}
δ(qB, b, B) = {(qB, B)}
δ(qB, a, B) = {(qA, AB)}
∀X ∈ {q0, qA, qB}, Y ∈ {A, B, Z} δ(X, ?, Y ) = {(q1, Y )},
δ(q1, a, A) = {(q1, ε)}
δ(q1, b, B) = {(q1, ε)}
δ(q1, ε, Z) = {(q2, ε)}
Jak jsme již zdůvodnili, platí Lε(A) = L.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.