IB102 úkol 6, příklad 2 Odevzdání: 4. 11. 2019
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 libovolný jazyk nad abecedou Σ = {a, b, c}.
Mějme operaci extend() takovou, že jazyk R = extend(L) obsahuje pro každé slovo w ∈ L množinu
modifikovaných slov W vzniklou tak, že každé písmeno ve slově w lze namnožit libovolně mnohokrát
(nemůže se ale ztratit). Tedy například pro slovo w = a dostáváme množinu slov W = {a}+.
Například:
extend({a}) = {a}+
extend({a, b}) = {a}+
∪ {b}+
extend({ab, abb}) = {a}+
· {b}+
extend({ε}) = {ε}
extend(∅) = ∅
extend({aabbb}) = {a} · {a}+
· ({bb} · {b}+
)
extend({aa}∗
) = {ε} ∪ ({aa} · {a}∗
)
extend({a}+
· {b}+
) = {a}+
· {b}+
Vaším úkolem je rozhodnout, zda pro každý regulární jazyk L je jazyk extend(L) taktéž regulární.
Tedy zda je třída regulárních jazyků uzavřená na operaci extend(). Uveďte vaše rozhodnutí a odpověď
dokažte, a to tak, že:
• Pokud rozhodnete, že třída regulárních jazyků není uzavřená na operaci extend(), najděte
regulární jazyk L takový, že jazyk extend(L) regulární není. Neregularitu extend(L) dokažte
buď odvoláním se na známe neregulární jazyky, nebo pomocí obměny lemmatu o vkládání
(Pumping lemma) nebo použitím Myhillovy-Nerodovy věty.
• 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ů (například transformací
automatu pro jazyk L na automat pro jazyk extend(L)).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.