0 Daumen
195 Aufrufe

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

Gefragt von

1 Antwort

+1 Punkt
 
Beste Antwort

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

  • |uv| ≤ n,
  • |v| > 0.

Eine solche Zerlegung existiert aufgrund des Pumping-Lemmas.

Dann ist entweder v = bai für ein i ∈ ℕ oder v = ai für ein i ∈ ℕ. In beiden Fällen ist uv2w ∉ L, was ein Widerspruch zum Pumping-Lemma  ist.

Beantwortet von

Vielen Dank.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...