IB102 – úkol 5, příklad 1 Odevzdání: 2. 11. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Nechť L a R jsou regulární jazyky nad abecedou Σ a operace inject(L, R)
je definována následovně:
inject(L, R) = {u · v · w | uw ∈ L, v ∈ R}
Intuitivně je tedy inject(L, R) jazyk obsahující všechna slova, která vzniknou vložením
libovolného slova z jazyka R někam do libovolného slova z jazyka L. Například:
inject({a, aa} , {b, bb}) = {ba, ab, bba, abb, baa, aba, aab, bbaa, abba, aabb}
inject({ε, a} , {a, ab}) = {a, ab, aa, aab, aba}
Vaším úkolem je rozhodnout, zda je jazyk inject(L, R) regulární, tedy že třída regulárních
jazyků je uzavřená na operaci inject. Vaši odpověď dokažte, a to tak, že:
• Pokud rozhodnete, že není, najděte regulární jazyky L a R takové, že jazyk inject(L, R)
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 ja-
zyků.