0 Daumen
356 Aufrufe

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

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.

von 1,4 k  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...