Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:37 Fr 22.08.2008 | | Autor: | TTaylor |
| Aufgabe | L= [mm]\{a^n b^m c^n| n>0, m>0\}[/mm]
Ist L regulär?
|
Annahme L ist regulär:
Ich wähle mir ein Wort w=[mm]a^n b^m c^n[/mm]
und für w= xyz gilt nach Pumping Lemma:
|y|=nicht leer
|xy|<= n
|xy| besteht nur aus a's.
Nach Pumping Lemma muss xz auch Element von L sein.
Da aber |y|nicht leer, kann xz nicht mehr als n-1 a's besitzen. --> L nicht regulär.
ich denke, dass der Beweis so nicht stimmt aber ich weiß nicht wie ich es anders machen soll. Brauche Hilfe!
Ich verstehe auch nicht warum für jede Zerlegung für w=xyz ;
|xy|*n gelten soll?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:09 Sa 23.08.2008 | | Autor: | uliweil |
> L= [mm]\{a^n b^m c^n| n>0, m>0\}[/mm]
> Ist L regulär?
>
Dein Beweis ist im wesentlichen richtig, es sind nur ein paar Schönheitsfehler drin:
>
> Annahme L ist regulär:
Aha, du behauptest also, L sei nicht regulär und willst das mit einem Widerspruchsbeweis zeigen.
Dann gibt es nach PL eine konstante Zahl (nenn sie wie du willst, aber n ist als Bezeichnung ungünstig, weil n ja schon in der Beschreibung der Sprache benutzt wird. Ich nenne sie jetzt mal k), sodass für alle Wörter w der Sprache mit |w| [mm] \ge [/mm] k gilt: ...
>
> Ich wähle mir ein Wort w=[mm]a^n b^m c^n[/mm]
Diese Wort musst du also so wählen, dass es garantiert mindestens die Länge k hat, dafür würde sich hier also w=[mm]a^k b^m c^k[/mm] anbieten, mit irgendeinem m (auch das kannst du wenn du willst festlegen: m = 1 oder m=k zum Beislpiel).
> und für w= xyz gilt
> nach Pumping Lemma:
>
> |y|=nicht leer
> |xy|<= n
Hier muss dann mit meinen Bezeichnungen |xy|<= k hin
Die Aussage des PL ist: es gibt eine Zerlegung in x, y, und z, sodass ...
Im indirekten Beweis musst du den Widerspruch für jede mögliche Zerlegung mit diesen Eigenschaften herleiten.
Dazu überlegst du richtig:
> |xy| besteht nur aus a's.
Dies ist also keine direkte Aussage des PL, sondern ein Folgerung aus den beiden ersten Eigenschaften und der Wahl deines Wortes
>
> Nach Pumping Lemma muss xz auch Element von L sein.
> Da aber |y|nicht leer, kann xz nicht mehr als n-1 a's
k-1 a's
> besitzen. --> L nicht regulär.
Diese Folgerung ist richtig, aber vielleicht etwas schnell (offenbar scheint sie ja dir selber nicht klar zu sein).
Also etwas ausführlicher:
Da |y| nicht leer ist und xy nur aus a's besteht, besteht auch y nur aus a's und zwar mindestens einem. Damit unterscheidet sich xz von w dadurch, dass mindestens ein a fehlt, die Anzahl der b's und c's aber unverändert ist. Also xz = [mm]a^p b^m c^k[/mm] mit p < k
Damit hat xz nicht die Gestalt [mm]a^n b^m c^n[/mm] (dh es hat nicht gleich viele a's wie c's) und ist deshalb nicht in L.
>
> ich denke, dass der Beweis so nicht stimmt aber ich weiß
> nicht wie ich es anders machen soll. Brauche Hilfe!
Wie gesagt, im wesentlichen war dein Beweis richtig.
>
> Ich verstehe auch nicht warum für jede Zerlegung für w=xyz
> ;
> |xy|*n gelten soll?
Diese Frage verstehe ich nicht. Was soll gelten?
Beste Grüße
Uli
|
|
|
|
