Pumping Lemma frage

06.01.2007, 20:30

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

06.01.2007, 23:03

Auf diesen Beitrag antworten »

Tobias

Also erstmal eine Nachfrage zu der Klammerung:

Ist $[latex]L = \big\{ a ^{\left(k^2\right)} \; | \; k \geq 1 \big\}[/latex]$ oder $[latex]L = \big\{ \left(a^k\right)^2 = a^{2k} \; | \; k \geq 1 \big\}[/latex]$ gemeint? Ich gehe mal vom ersten aus.

Nehmen wir mal an L sei eine reguläre Sprache. Dann existiert ein $[latex]n \in \mathbb{N}[/latex]$ , so dass sich alle $[latex]x \in L[/latex]$ mit $[latex]|x| \geq n[/latex]$ zerlegen lassen in [latex]x = uvw[/latex]

und alle

sind dann ebenfalls in L.

Wenn es dieses n gibt, dann ist auch $[latex]a^{(n^2)} = uvw \in L[/latex]$ .

Wir sagen: $[latex]u = a^q, \; v=a^r, \; w=a^s \quad q+r+s = n^2[/latex]$ .

Wegen der Bedingungen des Pumpinglemmas folgt: $[latex]1 \leq r \leq n[/latex]$ .

Dann folgern wir:

$[latex]|a^{(n^2)}| < |uv^2w| = |a^qa^{2r}a^s| = |a^{(n^2)}a^r| \leq |a^{(n^2)}a^n| < |a^{(n^2)}a^{2n}a| = |a^{(n+1)^2}|[/latex]$

Laut Pumpinglemma müsste [latex]uv^2w[/latex]

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.

07.01.2007, 00:35

Auf diesen Beitrag antworten »

foogi

Zitat:

Original von Tobias
Also erstmal eine Nachfrage zu der Klammerung:

Ist $[latex]L = \big\{ a ^{\left(k^2\right)} \; | \; k \geq 1 \big\}[/latex]$ oder $[latex]L = \big\{ \left(a^k\right)^2 = a^{2k} \; | \; k \geq 1 \big\}[/latex]$ 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 $[latex]n \in \mathbb{N}[/latex]$ , so dass sich alle $[latex]x \in L[/latex]$ mit $[latex]|x| \geq n[/latex]$ zerlegen lassen in [latex]x = uvw[/latex]

und alle

sind dann ebenfalls in L.

Wenn es dieses n gibt, dann ist auch $[latex]a^{(n^2)} = uvw \in L[/latex]$ .

Frage: ist das n in n^2 auch das n womit man die Zustände meint?

Wir sagen: $[latex]u = a^q, \; v=a^r, \; w=a^s \quad q+r+s = n^2[/latex]$ .

Wegen der Bedingungen des Pumpinglemmas folgt: $[latex]1 \leq r \leq n[/latex]$ .

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?

$[latex]|a^{(n^2)}| < |uv^2w| = |a^qa^{2r}a^s| = |a^{(n^2)}a^r| \leq |a^{(n^2)}a^n| < |a^{(n^2)}a^{2n}a| = |a^{(n+1)^2}|[/latex]$

Laut Pumpinglemma müsste [latex]uv^2w[/latex]

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.

07.01.2007, 13:57

Auf diesen Beitrag antworten »

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:

$[latex]a^{(n^2)} \in L[/latex]$

Ich habe angenommen, dass das Pumpinglemma erfüllt sei, also hat das von mir ausgesuchte Wort auf jeden Fall eine Zerlegung in $[latex]a^{(n^2)} = uvw[/latex]$ . Die Bedinungen des Lemmas sind unter anderem: $[latex]|v| \geq 1, \; |uv| \leq n[/latex]$ .

Ich kann nun mein Wort zerlegen: $[latex]a^{(n^2)} = a^qa^ra^s[/latex]$ , dann ist natürlich [latex]n^2 = q+r+s[/latex]

.
Meine Zerlegung ist durch die q, r, s beliebig und ich setze: $[latex]u=a^q, \; v=a^r, \; w=a^s[/latex]$ . Wegen $[latex]|v| \geq 1, \; |uv| \leq n[/latex]$ muss dann auch gelten $[latex]r \geq 1[/latex]$ und $[latex]q+r \leq n[/latex]$ . Aus diesen beiden Ungleichungen kann man ableiten $[latex]1 \leq r \leq n[/latex]$ . 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:

[latex]n^2 < |uv^2w| < (n+1)^2[/latex]

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.

07.01.2007, 14:35

Auf diesen Beitrag antworten »

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: $[latex]a^{(n^2)} = a^qa^ra^s[/latex]$ , dann ist natürlich [latex]n^2 = q+r+s[/latex]

.
Meine Zerlegung ist durch die q, r, s beliebig und ich setze: $[latex]u=a^q, \; v=a^r, \; w=a^s[/latex]$ . Wegen $[latex]|v| \geq 1, \; |uv| \leq n[/latex]$ muss dann auch gelten $[latex]r \geq 1[/latex]$ und $[latex]q+r \leq n[/latex]$ . Aus diesen beiden Ungleichungen kann man ableiten $[latex]1 \leq r \leq n[/latex]$ . 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..?

[latex]n^2 < |uv^2w| < (n+1)^2[/latex]

07.01.2007, 15:50

Auf diesen Beitrag antworten »

Tobias

Es geht darum die maximalen Grenzen von r auszuloten.

untere Schranke: $[latex]|v| = |a^r| = r \geq 1[/latex]$

obere Schranke: $[latex]|uv| = |a^qa^r| = q+r \leq n[/latex]$ . 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 $[latex]q \geq 0[/latex]$
$[latex]q+r \leq n \iff r \leq n-q \leq n[/latex]$

Wenn [latex]v = a^r[/latex]

dann ist $[latex]v^2 = a^{2r}[/latex]$ .

Somit ist wegen [latex]q+r+s = n^2[/latex]

07.01.2007, 16:15

Auf diesen Beitrag antworten »

foogi

ok. ich denke das müsste nun klar sein, falls ich dennoch was nicht verstanden habe, dann meld ich mich nochmal...

danke..

Daumen hoch

13.01.2007, 22:40

Auf diesen Beitrag antworten »

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: $[latex]|v| = |a^r| = r \geq 1[/latex]$

obere Schranke: $[latex]|uv| = |a^qa^r| = q+r \leq n[/latex]$ . 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 $[latex]q \geq 0[/latex]$
$[latex]q+r \leq n \iff r \leq n-q \leq n[/latex]$

Wenn [latex]v = a^r[/latex]

dann ist $[latex]v^2 = a^{2r}[/latex]$ .

Somit ist wegen [latex]q+r+s = n^2[/latex]

$[latex]uv^2w = a^qa^{2r}a^s = a^{q + 2r + s} = a^{q+r+s}a^r = a^{(n^2)}a^r[/latex]$

Wir kennen nun die Grenzen von r: $[latex]1 \leq r \leq n[/latex]$ :

$[latex]|a^{(n^2)}a| \leq |a^{(n^2)}a^r| \leq |a^{(n^2)}a^n|[/latex]$

$[latex]a^{(n^2)}a^r[/latex]$ liegt also immer zwischen zwei Quadratzahlen, denn

und wie siehst du das? das die zwischen zwei quadratzahlen liegen

$[latex]|a^{(n^2)}a| > a^{(n^2)}[/latex]$
$[latex]|a^{(n^2)}a^n| < |a^{((n+1)^2)}|[/latex]$

den letzten Vergleich verstehe ich nicht, und wie kommst du auf
$[latex]{((n+1)^2)}[/latex]$ woher kommt das?

Sorry für die vielleicht dummen fragen, aber habs noch nicht ganz drauf..

14.01.2007, 20:12

Auf diesen Beitrag antworten »

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:
[latex](n+1)^2 = n^2 + 2n + 1[/latex]

Und das ist nunmal echt größer als
[latex]n^2+n[/latex]

Also $[latex]n^2+r \leq n^2+n < (n+1)^2[/latex]$

15.01.2007, 15:31

Auf diesen Beitrag antworten »

foogi

ok danke, die Aufgabe hab ich nun verstanden, allerdings fehlt mir noch einiges um andere Aufgaben selbst Lösen zu können.

Neue Frage »

Antworten »

Pumping Lemma frage

Verwandte Themen