Revision [6548]
This is an old revision of FormaleSprachen made by ToBo on 2008-11-19 02:01:05.
Formale Sprachen
Formale Sprachen - die Sprache endlicher Zustandsautomaten (SkriptAtfsEckNr1, S. 25)
1. Struktureigenschaften regulärer Sprachen
L ist eine reguläre Sprache über X.
Es gibt ein n ∈ N entsprechend PL
so, dass für alle x ∈ L mit
| ≥ n gilt: Es gibt Teilwörter u, v, w ∈ X* mit
| ≥ 1 und
2. Pumping-LemmaPumping-Lemma (PL) liefert eine notwendige Bedingung für reguläre Sprachen. Die Umkehrung des PL liefert die Möglichkeit, Sprachen auf Regularität zu überprüfen. Genauer gesagt liefert das PL die Möglichkeit den Beweis zu erbringen, dass eine formale Sprache nicht regulär ist. Allerdings kann der Beweis, dass eine formale Sprache regulär ist mit dem PL nicht erbracht werden. Beispiel 1Eine Sprache L ist definiert durch L = {x ∈ {a, b}* | x = akbk, k ∈ N} Beispiel 2L = {an b2n, | n ∈ N} 1. wähle n entsprechend PL 2. wähle Exemplaar x ∈ L: an b2n 3. Betrachte Zerlegungen in Teilweörter 4. Feststellung für alle diese Zerlegungen v in an 5. ⇒ uviw nur a's vervielfältigt ⇒ 2|uviw|a ≠ |uviw|a Siehe auch • |
