Die letzten 10 Beiträge |
foogi |
ok danke, die Aufgabe hab ich nun verstanden, allerdings fehlt mir noch einiges um andere Aufgaben selbst Lösen zu können. |
Tobias |
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 |
foogi |
Zitat: |
so un habe ich mich nochmal damit beschäftigt, ich kann nun fast alles nachvollziehen, leider felht noch etwas..
Es geht darum die maximalen Grenzen von r auszuloten.
.. geht es im Pumping Lemma immer darum?
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
und wie siehst du das? das die zwischen zwei quadratzahlen liegen
den letzten Vergleich verstehe ich nicht, und wie kommst du auf
woher kommt das?
|
Sorry für die vielleicht dummen fragen, aber habs noch nicht ganz drauf.. |
foogi |
ok. ich denke das müsste nun klar sein, falls ich dennoch was nicht verstanden habe, dann meld ich mich nochmal...
danke..
|
Tobias |
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
|
foogi |
erstmal finde ich es super das du so schnell und ausführlich geantwortet hast...
Doch zwei fragen hätte ich noch dazu..
Zitat: |
Original von Tobias
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.
kann ich hier einfach q=0 setzten? und wieso?
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:
genau hier das aufpumpen.. wie hast du das genau gemacht, also wei kommst du auf (n+1)^2.. und wieso soll das größer sein als das augepumpte..?
|
|
Tobias |
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. |
foogi |
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. |
|
Tobias |
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. |
foogi |
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 |
|
|