Pumping-Lemma |
| 14.12.2004, 11:17 | crackXs | Auf diesen Beitrag antworten » |
| Pumping-Lemma ich habe eine Frage zum Pumping-Lemma: Bei welcher Sprache ist das Pumping-Lemma erfüllt, die Sprache aber nicht regulär)? Gruß Jan |
||
| 15.12.2004, 08:02 | user444 | Auf diesen Beitrag antworten » |
| Pumping-Lemma Es gibt übrigens 2 Pumping Lemmas: eins für reguläre Sprachen (a) und eins für kontektfreie (b). Offensichtlich handelt es sich hierbei um (a). L ={ a^p b^m, p>m} ist nicht regulär. Ein Wort aus L läßt sich aber Zerlegen in u=a^p-1, v=a, w=b^m, n=p+m, so daß u v^i w = a^(p+i-1) b^m in L liegt für natürliches i. Denn es gilt p+i-1 >= p > m. cu |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
