Pumping-Lemma

Das Pumping-Lemma folgt aus den regulären Sprachen. Um zu zeigen, dass eine Sprache nicht regulär ist, wird erst davon ausgegangen und dann zu einem Widerspruch geführt.

Sei eine Reguläre Sprache. Dann gibt es eine Pumping-Zahl , so dass sich alle Wörter mit Mindestlänge zerlegen lassen in , so dass

Tip

Wir werden versuchen, einen Teil von auf- oder abzupumpen, sodass dann w nicht mehr in der Sprache enthalten ist. Dieer Teil ist in unserem Fall . Deswegen sollten wir für ein Wort wählen, was Teil der Sprache ist aber fast nicht mehr.

Beispiel

Dyck-Sprache

Gegeben:

Beispiele:

Beweis:

• Annahme: regulär, dann sei die Pumpingzahl.
• Wähle und
• Zerlege in (1), (2), (3) müssten erfüllt sein setzen sich nur aus dem Buchstaben zusammen
• Wegen folgt (2)
• Wort abpumpen:
• Daraus folgt, dass das abgepumpte Wort ein weniger als -s hat

Anzahl ist nicht gleich Anzahl

Wiederspruch, Annahme Falsch, nicht regulär

[!example] Beispiel: Sprache für Wörter mit mehr -s als -s

Sprache:

Beweis:

• Sei gegeben.
• Setze
• Sei Zerlegung mit und gegeben.
• Setze . Dann ist , denn besteht nur aus -s.
• Somit ist