IB102 – úkol 2, příklad 2 – řešení Odevzdání: 30. 9. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažme jazyk
L = {w ∈ {a, b, c}∗
| #a(w) + #b(w) = #c(w)}.
Rozhodněte, zda je jazyk L regulární, a vaše tvrzení dokažte. Tzn.:
• Pokud L je regulární, uveďte regulární gramatiku, která L generuje, nebo konečný
deterministický automat, který L akceptuje. Gramatiku/automat zapište se všemi
formálními náležitostmi.
• Pokud L není regulární, dokažte tuto skutečnost pomocí Lemmatu o vkládání (Pumping
lemma).
Řešení: Jazyk L není regulární.
Důkaz. Pro důkaz sporem předpokládejme, že jazyk L je regulární. Tudíž podle lemmatu
o vkládání existuje n ∈ N takové, že libovolné slovo w ∈ L, jehož délka je alespoň n, lze
psát ve tvaru w = xyz, kde |xy| ≤ n, y = ε a xyi
z ∈ L pro každé i ∈ N0.
• Buď tedy n ∈ N libovolné přirozené číslo, dále však pevné.
• Uvažme slovo w = an
bn
c2n
. Délka w je 4n ≥ n a w jistě patří do jazyka L.
• Slovo w lze tedy psát ve tvaru w = xyz, kde |xy| ≤ n a y = ε. Libovolné rozdělení
splňující tyto podmínky musí mít následující tvar:
x = ak
0 ≤ k < n
y = al
0 < l ≤ n − k
z = an−k−l
bn
c2n
• Z lemmatu o vkládání víme, že xyi
z ∈ L pro každé i ∈ N0. Zejména tedy volbou
i = 0 dostáváme xy0
z = xz ∈ L.
• Ale xz ∈ L, neboť xz = an−l
bn
c2n
a (n − l) + n = 2n (protože l > 0).
• Předpoklad regularity jazyka L tedy vede ke sporu, takže L regulární není.
1