IB102 – úkol 5, příklad 2 Odevzdání: 21. 10. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ je libovolná abeceda a removeFirst : 2Σ∗
→ 2Σ∗
je unární operace
nad jazyky definovaná následovně:
removeFirst(L) = {w ∈ Σ∗
| ∃x ∈ Σ . xw ∈ L}
Intuitivně: removeFirst(L) je jazyk, který vznikne z L odstraněním prvního písmene ze
všech slov délky alespoň jedna. Například
removeFirst({ε, aa, aba}) = {a, ba}
removeFirst({b, ab, abba}) = {ε, b, bba}
Rozhodněte, zda je třída všech regulárních jazyků nad abecedou Σ uzavřená na operaci
removeFirst, a vaše tvrzení dokažte. Tzn.:
• Pokud je vaše odpověď kladná, dokažte, že pro libovolný regulární jazyk L ⊆ Σ∗
je
jazyk removeFirst(L) také regulární.
• Pokud je vaše odpověď záporná, najděte abecedu Σ a jazyk L ⊆ Σ∗
, který je regulární,
ale jazyk removeFirst(L) regulární není.
1