IB005 úkol 6, příklad 2 Odevzdání: 1. 4. 2024 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 →
← : 2Σ∗
→ 2Σ ∗
, kde Σ =
x
y
| x, y ∈ Σ , takovou, že jazyk
→
←(L) =
w
v
| w ∈ L, v ∈ LR
, |w| = |v| ⊆ Σ ∗
obsahuje právě pro každou dvojici stejně dlouhých slov u ∈ L a v ∈ LR modifikované slovo w, které
vznikne umístěním u nad v.
Například tedy:
→
←({a, b, c}) =
a
a
,
a
b
,
a
c
,
b
a
,
b
b
,
b
c
,
c
a
,
c
b
,
c
c
→
←({ab, ba, abc}) =
ab
ab
,
ab
ba
,
ba
ab
,
ba
ba
,
abc
cba
→
←(∅) = ∅
→
←({ε}) = {ε}
→
←(Σ∗
) = Σ ∗
Vaším úkolem je rozhodnout, zda pro každý regulární jazyk L je jazyk →
←(L) taktéž regulární. Tedy
zda je třída regulárních jazyků uzavřená na operaci →
←. Uveďte své rozhodnutí a odpověď dokažte,
a to tak, že:
• Pokud rozhodnete, že třída regulárních jazyků není uzavřená na operaci →
←, najděte regulární
jazyk L takový, že jazyk →
←(L) regulární není. Neregularitu jazyka →
←(L) dokažte buď odvoláním
se na známé neregulární jazyky, 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í buď 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 →
←(L)). Správnost svého 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.