IB102 úkol 5, příklad 1 Odevzdání: 24. 10. 2016
Jméno: UČO: Skupina:
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]
Nechť L je regulární jazyk nad libovolnou abecedou Σ a unární operace removeOne(L) je definována
následovně:
removeOne(L) = {uv ∈ Σ∗
| ∃x ∈ Σ takové, že uxv ∈ L}
Intuitivně je tedy removeOne(L) jazyk obsahující všechna slova w taková, že w vznikne odstraněním
jednoho písmene z nějakého slova délky alespoň jedna z jazyka L. Například:
removeOne({b, abab}) = {ε, bab, aab, abb, aba}
removeOne({ε, ab, bba, ababab}) = {a, b, ba, bb, babab, aabab, abbab, abaab, ababb, ababa}
removeOne({a}+
) = {a}∗
removeOne({aa}∗
) = {a} · {aa}∗
Vaším úkolem je rozhodnout, zda je jazyk removeOne(L) regulární, tedy že třída regulárních jazyků
je uzavřená na operaci removeOne. Vaši odpověď dokažte, a to tak, že:
• Pokud rozhodnete, že není, najděte regulární jazyk L takový, že jazyk removeOne(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.
IB102 úkol 5, příklad 1 Odevzdání: 24. 10. 2016
Jméno: UČO: Skupina:
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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.