Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma frage

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Pumping Lemma frage

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

Pumping Lemma frage

Zitatantwort auf diesen Beitrag erstellen

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 20:30

Nehmen Sie foogi in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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.

06.01.2007 23:03

Nehmen Sie Tobias in Ihre Freundesliste auf

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von foogi: 07.01.2007 00:39.

07.01.2007 00:35

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 07.01.2007 13:59.

07.01.2007 13:57

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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 14:35

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 15:50

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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

danke..

Daumen hoch

07.01.2007 16:15

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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..

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von foogi: 13.01.2007 22:42.

13.01.2007 22:40

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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]$

14.01.2007 20:12

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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

15.01.2007 15:31

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma frage