Reguläre Sprache+PumpingLemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:18 Sa 22.10.2011 | | Autor: | Erbse |
Wir haben bei uns reguläre Sprachen folgendermaßen definiert:
1) L ={a} a [mm] \in [/mm] E
oder
2) L = [mm] \emptyset
[/mm]
... und weitere
Wie kann ich dann bitte auf die Leere Menge das Pumping-Lemma anwenden?
Oder auf Punkt 2?
z.B. L = {a}
Dann müsste u,x = [mm] \varepsilon [/mm] v = a sein (geht ja sonst nicht anders?)
Aber u * [mm] v^{2} [/mm] * x = aa [mm] \not\in [/mm] L
Da muss doch irgendwas bei der Definition der regulären Sprachen nicht stimmen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:07 Sa 22.10.2011 | | Autor: | felixf |
Moin!
> Siehe unten.
> Wir haben bei uns reguläre Sprachen folgendermaßen
> definiert:
Naja, das ist jetzt keine Definition, sondern Beispiele fuer Sprachen, die die Definition erfuellen.
> 1) L ={a} a [mm]\in[/mm] E
> oder
> 2) L = [mm]\emptyset[/mm]
> ... und weitere
>
> Wie kann ich dann bitte auf die Leere Menge das
> Pumping-Lemma anwenden?
> Oder auf Punkt 2?
> z.B. L = {a}
> Dann müsste u,x = [mm]\varepsilon[/mm] v = a sein (geht ja sonst
> nicht anders?)
> Aber u * [mm]v^{2}[/mm] * x = aa [mm]\not\in[/mm] L
> Da muss doch irgendwas bei der Definition der regulären
> Sprachen nicht stimmen.
Das Pumping-Lemma sagt doch, dass man die Zerlegung nur fuer Worte bekommt, die eine gewisse Mindestlaenge ist. Wenn du die Mindestlaenge bei den obigen Sprachen als etwa 2 vorgibst, gibt es kein Wort welches die erfuellt, und somit auch kein Wort fuer welches die Pumping-Lemma-Bedingung gelten muss.
Und bei der leeren Sprache ist es noch einfacher: das Pumping-Lemma sagt ja, dass fuer jedes Wort in der Sprache mit bestimmten Anforderungen etwas gelten muss. Da es aber kein Wort gibt, ist es voellig egal was die Anforderungen oder Folgerungen sind: das Statement ist immer wahr.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:14 Sa 22.10.2011 | | Autor: | Erbse |
Danke okey das macht sinn.
Das heißt, dass bei unendlichen regulären Sprachen immer Wörter existieren auf die man das Pumping-Lemma anwenden kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:43 Sa 22.10.2011 | | Autor: | felixf |
Moin!
> Danke okey das macht sinn.
> Das heißt, dass bei unendlichen regulären Sprachen immer
> Wörter existieren auf die man das Pumping-Lemma anwenden
> kann.
Genau. Es ist sogar so, dass die Aussage bei endlichen Sprachen niemals auf ein Wort anwendbar ist; andernfalls wuerdest du aus so einem Wort ja unendlich viele weitere verschiedene Woerter in der Sprache konstruieren koennen, was ein Widerspruch dazu ist dass die Sprache endlich ist.
LG Felix
|
|
|
|
