0 Daumen
855 Aufrufe

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

Avatar von

1 Antwort

+1 Daumen
 
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.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community