Zeigen Sie mit Hilfe des Pumping-Lemmas,

Question 1

dass die Sprache L = {baⁿbaⁿb | n ≥ 1} nicht regulär ist.

Question 2

Angenommen L ist regulär. Seien n,m ∈ ℕ mit m > n. Ferner sei uvw eine Zerlegung von z:=ba^mba^mb ∈ L, so dass

Eine solche Zerlegung existiert aufgrund des Pumping-Lemmas.

Dann ist entweder v = baⁱ für ein i ∈ ℕ oder v = aⁱ für ein i ∈ ℕ. In beiden Fällen ist uv²w ∉ L, was ein Widerspruch zum Pumping-Lemma ist.

oswald · Answer 1 · 2017-05-22T02:31:23+0000

Angenommen L ist regulär. Seien n,m ∈ ℕ mit m > n. Ferner sei uvw eine Zerlegung von z:=ba^mba^mb ∈ L, so dass

Eine solche Zerlegung existiert aufgrund des Pumping-Lemmas.

Dann ist entweder v = baⁱ für ein i ∈ ℕ oder v = aⁱ für ein i ∈ ℕ. In beiden Fällen ist uv²w ∉ L, was ein Widerspruch zum Pumping-Lemma ist.

1 Antwort