IB005 úkol 6, příklad 2 Odevzdání: 4. 4. 2022 12:00
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. [0,5 bodu] Nechť L je libovolný jazyk nad abecedou Σ = {a, b, c}.
Mějme operaci EvenCensor() takovou, že jazyk R = EvenCensor(L) obsahuje pro každé slovo w ∈ L
modifikované slovo w′ vzniklé tak, že každé druhé písmeno slova w nahradíme za #.
Formálně definujeme operaci následovně (použijeme pomocnou operaci wEvenCensor() operující
nad slovy):
wEvenCensor(ε) = ε
wEvenCensor(d) = d pro d ∈ Σ
wEvenCensor(dew) = d · # · wEvenCensor(w) pro d, e ∈ Σ, w ∈ Σ∗
EvenCensor(L) = {wEvenCensor(w) | w ∈ L}
Například tedy:
EvenCensor({a, b, c}) = {a, b, c}
EvenCensor({ab, a}) = {a#, a}
EvenCensor(∅) = ∅
EvenCensor({ε}) = {ε}
EvenCensor({aba, aca, bacabac, abcc}) = {a#a, b#c#b#c, a#c#}
EvenCensor(Σ∗
) = {a#, b#, c#}∗
· {ε, a, b, c}
Vaším úkolem je rozhodnout, zda pro každý regulární jazyk L je jazyk EvenCensor(L) taktéž regulární.
Tedy zda je třída regulárních jazyků uzavřená na operaci EvenCensor(). 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 EvenCensor(), najděte
regulární jazyk L takový, že jazyk EvenCensor(L) regulární není. Neregularitu jazyka
EvenCensor(L) dokažte buď odvoláním se na známé 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 EvenCensor(L)). Správnost vašeho algoritmu
nemusíte dokazovat.
Poznámka: Pokud píšete řešení v TEXu, před odevzdáním prosím odmažte zadání.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.