Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Pumping Lemma frage (http://www.informatikerboard.de/board/thread.php?threadid=122)
Geschrieben von foogi am 06.01.2007 um 20:30:
Pumping Lemma frage
hallo,
ich komme da grad echt nicht weiter, denke auch das mir die Mathekentnisse auch wieder fehlen...
folgendes:
wie kann ich den bei dieser Sprache beweisen, das sie nicht regulär ist. Mit dem Pumping Lemma.
L={ a ^k^2| k>=1}
Annahmeist ja es gibt einen DFA der die Sprache L aktzeptiert.
dann muss |x|>=n sein. sprich di Wortlänge muss größer der Zustände sein.
und x= uvw
dann wähle ich mal ein Wort= a^n ... so nun weiß aber nciht weiter, wie ich das nun zerteilen kann, bzw sollte??
kann mir da jemand helfen?
danke
Geschrieben von Tobias am 06.01.2007 um 23:03:
Also erstmal eine Nachfrage zu der Klammerung:
Ist
oder
gemeint? Ich gehe mal vom ersten aus.
Nehmen wir mal an L sei eine reguläre Sprache. Dann existiert ein
, so dass sich alle
mit
zerlegen lassen in
und alle
sind dann ebenfalls in L.
Wenn es dieses n gibt, dann ist auch
.
Wir sagen:
.
Wegen der Bedingungen des Pumpinglemmas folgt:
.
Dann folgern wir:
Laut Pumpinglemma müsste
ebenfalls in L liegen. Aber die Wortlänge liegt echt zwischen zwei Quadratzahlen, also nicht in L. Das ist ein Widerspruch, d.h. die Sprache ist nicht regulär.
Geschrieben von foogi am 07.01.2007 um 00:35:
Zitat: |
Original von Tobias
Also erstmal eine Nachfrage zu der Klammerung:
Ist oder gemeint? Ich gehe mal vom ersten aus.
ja da keine Klammerung da ist gehe ich auch vom ersten aus..
Nehmen wir mal an L sei eine reguläre Sprache. Dann existiert ein , so dass sich alle mit zerlegen lassen in und alle sind dann ebenfalls in L.
Wenn es dieses n gibt, dann ist auch .
Frage: ist das n in n^2 auch das n womit man die Zustände meint?
Wir sagen: .
Wegen der Bedingungen des Pumpinglemmas folgt: .
Dann folgern wir:
hmm das verstehe ich nicht ganz.. vielleicht kannst du mir mal die Schritte erklären, wie du von einem zum anderen kommst..
vor allem die Ausdrücke die du gleichgesetzt hast, welche Schritte hast du dabei vollzogen?
Laut Pumpinglemma müsste ebenfalls in L liegen. Aber die Wortlänge liegt echt zwischen zwei Quadratzahlen, also nicht in L. Das ist ein Widerspruch, d.h. die Sprache ist nicht regulär. |
Geschrieben von Tobias am 07.01.2007 um 13:57:
Das n ist natürlich (indirekt) abhängig von der Anzahl der Zustände. Denn wenn man eine unendliche Sprache hat (also die Wörter beliebig lang werden können) aber diese Sprache von einem endlichen Automaten erkannt werden soll, dann muss der Automat für Wörter ab einer bestimmten Länge (diese Länge ist das n) eine Schleife laufen, denn er hat ja nur endlich viele Zustände. Diese Schleife kann man beliebig oft laufen, was dem "Aufpumpen" im Pumpinglemma entspricht.
Zu meinem Beweis:
Es gilt die Beziehung:
Sprache ist regulär ==> Sprache erfüllt das Pumpinglemma (andersrum nicht unbedingt).
Daraus kann man logisch folgern:
Sprache erfüllt nicht das Pumpinglemma ==> Sprache ist nicht regulär.
Mein Ansatz ist nun indirekt: Angenommen L erfülle das Pumpinglemma, dann muss es irgendein n geben, so dass alle Wörter, die größer sind als n eine Zerlegung uvw besitzen und man das v in dieser Zerlegung beliebig "aufpumpen" kann so dass das aufgepumpte Wort wieder in L liegt.
Ich gehe also erstmal davon aus, dass dieses n existiert ohne es genauer zu benennen. Wenn es dieses n gibt, dann konstruiere ich mir ein Wort aus L, das größer ist als n:
Ich habe angenommen, dass das Pumpinglemma erfüllt sei, also hat das von mir ausgesuchte Wort auf jeden Fall eine Zerlegung in
. Die Bedinungen des Lemmas sind unter anderem:
.
Ich kann nun mein Wort zerlegen:
, dann ist natürlich
.
Meine Zerlegung ist durch die q, r, s beliebig und ich setze:
. Wegen
muss dann auch gelten
und
. Aus diesen beiden Ungleichungen kann man ableiten
. Die obere Schranke entsteht, wenn man q=0 setzt.
Nun pumpe ich die Zerlegung um eins auf. Dann leite ich mit der im vorigen Beitrag aufgestellten Ungleichung her, dass das aufgepumpte Wort zwischen zwei direkt benachbarten Quadratzahlen liegt:
Also kann es nicht in der Sprache liegen. Das verletzt das Pumpinglemma und wir erhalten einen Widerspruch zur Annahme, dass es erfüllt sei.
Also kurz:
Angenommen es gibt ein n.
Betrachte eine beliebige Zerlegung, die wir bis auf die Bedingungen des Pumpinglemmas nicht einschränken. (Das ist wichtig, denn man muss ja prüfen, dass es keine gültige Zerlegung gibt, also muss man es für alle Zerlegungen prüfen.)
Pumpe die Zerlegung auf und führe einen Widerspruch herbei. Also gibt es keine gültige Zerlegung.
Geschrieben von Tobias am 07.01.2007 um 15:50:
Es geht darum die maximalen Grenzen von r auszuloten.
untere Schranke:
obere Schranke:
. Das Lemma verbietet uns nicht q=0 und somit u=leeres Wort zu setzen. Nur mit q=0 kann man r maximal wählen, denn es gilt wegen
Wenn
dann ist
.
Somit ist wegen
Wir kennen nun die Grenzen von r:
:
liegt also immer zwischen zwei Quadratzahlen, denn
Geschrieben von foogi am 07.01.2007 um 16:15:
ok. ich denke das müsste nun klar sein, falls ich dennoch was nicht verstanden habe, dann meld ich mich nochmal...
danke..
Geschrieben von Tobias am 14.01.2007 um 20:12:
Nein, das mit dem r kann doch garnicht verallgemeinert werden, denn das r ist ja sprachenspezifisch. Wenn ich das v aufpumpe, dann vervielfache ich das r. Wenn ich die Schranken von r kenne, so auch die Schranken für Vielfache von r. Daraus kann ich dann Informationen ziehen. Steht alles in mehrfacher Ausführung in diesem Thread.
Dass zwischen n und n+1 keine weitere ganze Zahl liegt ist klar. Ebenso folgt dann aber, dass zwischen n^2 und (n+1)^2 keine weitere Quadratzahl liegt.
Die binomische Formel sagt:
Und das ist nunmal echt größer als
Also
Geschrieben von foogi am 15.01.2007 um 15:31:
ok danke, die Aufgabe hab ich nun verstanden, allerdings fehlt mir noch einiges um andere Aufgaben selbst Lösen zu können.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH