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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.