0 Daumen
96 Aufrufe

Frage:

Zeigen Sie mit Hilfe des Pumping-Lemmas, dass die folgenden Sprachen über dem Alphabet {a, b, c}
nicht regulär sind.


L₁ = {c^i a^j cb^{i+j}   | i, j ∈ N₀}


Kann mir hier jemand weiterhlefen? Ich komme leider nicht weiter

von

1 Antwort

0 Daumen

Sei \(p\in \mathbb{N}\).

Gib ein Wort \(w\in L_1\) an, so dass

  • \(w\) mindestens die Länge \(p\) hat und

  • jede Zerlegung \(w = xyz\) mit

    • \(|xy| \leq p\)
    • \(|y| \neq 0\)

    die Eigenschaft hat, dass es ein \(i\in \mathbb{N}_0\) mit \(xy^iz\notin L_1\) gibt.

von 4,0 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community