0 Daumen
197 Aufrufe

Zeigen Sie mit dem Pumping-Lemma für reguläre Sprachen, dass die folgende Sprache nicht regulär ist:

L = {o^m 1^k | 0 ≤ m ≤ k, m, k ∈ ℕ} ⊆ {0, 1}*.

Gefragt von

1 Antwort

+1 Punkt
 
Beste Antwort

Angenommen L sei regulär.

Sei n∈ℕ die Pumping-Zahl.

Es ist 0^n 1^n ∈ L.

Laut Pumping-Lemma ist dann auch 0^{n+k} 1^n ∈ L für ein k > 0.

Beantwortet von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...