IB102 úkol 6, příklad 2 Odevzdání: 29. 10. 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.
2. [2 body] Nechť L je regulární jazyk nad abecedou Σ = {a, b, c}.
Mějme operaci changeWhileNotA() takovou, že jazyk R = changeWhileNotA(L) obsahuje pro každé
slovo w ∈ L modifikované slovo w vzniklé tak, že v začátku slova w, před prvním výskytem písmene
a, se všechna písmena b nahradí za písmena c a všechna písmena c se nahradí za písmena b. Pokud
se ve slově w žádné písmeno a nenachází, pak dojde k těmto náhradám v celém slově.
Například:
changeWhileNotA({ε, a, bcba, bacab}) = {ε, a, cbca, cacab}
changeWhileNotA({b, cbc, aba, bcabac}) = {c, bcb, aba, cbabac}
changeWhileNotA({bca}+
) = {cba} · {bca}∗
changeWhileNotA({bc}+
) = {cb}+
changeWhileNotA(∅) = ∅
Vaším úkolem je rozhodnout, zda pro každý regulární jazyk L je jazyk changeWhileNotA(L) taktéž
regulární. Tedy zda je třída regulárních jazyků uzavřená na operaci changeWhileNotA(). Vaši
odpověď dokažte, a to tak, že:
• Pokud rozhodnete, že není, najděte regulární jazyk L takový, že jazyk changeWhileNotA(L)
regulární není.
• Pokud rozhodnete, že je, dokažte tvrzení například s pomocí známých uzávěrových vlastností
třídy regulárních jazyků prezentovaných na přednášce, nebo konstruktivně popsáním algoritmu
na transformaci nějakého formalizmu pro popis regulárních jazyků.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.