IB102 – úkol 5, příklad 2 – řešení 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í.
Řešení: Třída všech regulárních jazyků nad abecedou Σ je uzavřená na operaci
removeFirst pro libovolnou abecedu Σ.
Důkaz. Buď Σ libovolná abeceda a L ⊆ Σ∗
regulární jazyk. Pak existuje deterministický
konečný automat A = (Q, Σ, δ, q0, F), který jazyk L akceptuje. Ukážeme, jak zkonstruovat
nedeterministický konečný automat s ε-kroky A , který akceptuje jazyk removeFirst(L),
a tudíž, že jazyk removeFirst(L) je také regulární.
Automat A zkonstruujeme tak, že k automatu A přidáme nový iniciální stav q0 a
z něj ε-přechody do všech stavů, do kterých se dá jedním krokem dostat z původního
iniciálního stavu q0. Tuto intuici nyní zachytíme formálně a ukážeme, že takto vytvořený
automat skutečně akceptuje jazyk removeFirst(L).
Buď X ⊆ Q množina definovaná následovně:
X = {δ(q0, x) | x ∈ Σ}
Tedy X je přesně množina popsána výše – množina všech stavů, do kterých se dá v automatu
A dostat ze stavu q0 jedním krokem. Buď dále q0 nový stav, tedy q0 ∈ Q. Definujeme
novou přechodovou funkci δ : (Q ∪ {q0}) × (Σ ∪ {ε}) → 2Q
:
δ (q, x) = {δ(q, x)} pro všechna q ∈ Q a všechna x ∈ Σ
δ (q, ε) = ∅ pro všechna q ∈ Q
δ (q0, x) = ∅ pro všechna x ∈ Σ
δ (q0, ε) = X
1
IB102 – úkol 5, příklad 2 – řešení Odevzdání: 21. 10. 2013
Vypracoval(a): UČO:
Skupina:
Pak hledaný automat A je (Q ∪ {q0}, Σ, δ , q0, F). Zbývá nám ukázat, že automat A
skutečně akceptuje jazyk removeFirst(L) – tj. L(A ) = removeFirst(L). Ukážeme obě
inkluze:
Nejdříve ukážeme, že L(A ) ⊆ removeFirst(L).
Nechť tedy w = a1 . . . an ∈ L(A ) je libovolné slovo akceptované automatem A (kde
n ∈ N0 a ai ∈ Σ pro všechna 1 ≤ i ≤ n). Tudíž v přechodovém grafu automatu A existuje
cesta
q0
ε
−→ q1
a1
−→ q2
a2
−→ · · ·
an
−→ qn+1
pro nějaké stavy q1, . . . , qn ∈ Q a qn+1 ∈ F. První přechod musí být pod slovem ε, protože
podle definice funkce δ ze stavu q0 nevedou jiné přechody než ε-přechody. Z definice
funkce δ navíc víme, že q1 ∈ X a tedy existuje písmeno x ∈ Σ takové, že q1 = δ(q0, x).
Takže v přechodovém grafu automatu A existuje cesta
q0
x
−→ q1
a1
−→ q2
a2
−→ · · ·
an
−→ qn+1
(protože automat A se na stavech z Q chová stejně jako automat A ). Protože qn+1 ∈ F,
automat A akceptuje slovo xw a proto xw ∈ L. A tedy w ∈ removeFirst(L).
Dále ukážeme, že removeFirst(L) ⊆ L(A ).
Nechť tedy w = a1 . . . an ∈ removeFirst(L) je libovolné (kde n ∈ N0 a ai ∈ Σ pro
všechna 1 ≤ i ≤ n). Tedy z definice operace removeFirst existuje x ∈ Σ takové, že
xw ∈ L. Tudíž v přechodovém grafu automatu A existuje cesta
q0
x
−→ q1
a1
−→ q2
a2
−→ · · ·
an
−→ qn+1
pro nějaké stavy q1, . . . , qn ∈ Q a qn+1 ∈ F. Pak z definice množiny X víme, že q1 ∈ X.
Takže q1 ∈ δ (q0, ε) a proto v přechodovém grafu automatu A existuje cesta
q0
ε
−→ q1
a1
−→ q2
a2
−→ · · ·
an
−→ qn+1
(protože automat A se na stavech z Q chová stejně jako automat A). Protože qn+1 ∈ F,
automat A akceptuje slovo w a proto w ∈ L(A ).
Celkově jsme dokázali L(A ) = removeFirst(L), tudíž jazyk removeFirst(L) je regulární,
protože je akceptovaný nedeterministickým konečným automatem A .
2