pumping lemma - Druckversion
+- FB18.de - Das Informatikforum ( /mybb ) +-- Forum: Bachelorstudieng ( /forumdisplay.php?fid=112 ) +--- Forum: PM Formale Informatik ( /forumdisplay.php?fid=99 ) +--- Thema: pumping lemma ( /showthread.php?tid=8705 ) |
pumping lemma - Anonymer User - 14.07.2007 20:15 hallo, wofür genau ist nochmal die natürlicher zahl (pumping length) gut? ah schreibt doch einfach mal alles was euch dazu einfällt bitte. ich bin grad ein bisschen wirr... RE: pumping lemma - Anonymer User - 14.07.2007 22:27 Das ist eine frei wählbare Zahl, für die gilt: |w|>=n Nehmen wir als Beispiel die Sprache a^m*b^2*c^m (m aus N) Ein (einfaches)Wort aus der Sprache wäre: a^n*b^2*c^n (n aus N) |w|= n +2 +n =2n +2 >= n(Pumping-Länge) Du könntest auch 2n als Pumping-Länge nehmen oder n/2 oder sogar 2n+2.Das tut man aber einfachheithalber nicht.Du sollst dir die Länge so wählen, dass es dir möglichst leicht fällt, den Widerspruchsbeweis durchzuführen. Ein anderes Beispiel: a^2*b^3*c^4 es gibt also keine Variablen, somit wird die Sprache von einem einzigen Wort gebildet. |w|=2+3+4=9 Ich wähle mir als P-Länge (n=)2 1.|uv|>= 1 2. |v| größer Null 3. für ein beliebiges i aus N muss u*v^i*w aus der Sprache sein.Wenn ich als i 100 wähle, dann ist ein so gebildetes Wort nicht drin. Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist. Ich wollte dir aber mit diesem besonderen Beispiel zeigen, dass die Pumping-Länge auch eine Zahl sein kann-wenngleich selten. RE: pumping lemma - UncleOwen - 15.07.2007 18:17
Anonymer User schrieb:
Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist.
RE: pumping lemma - Jan - 15.07.2007 20:24 Hab das hier grad gefunden. Ich finde, da wird das Ganze recht gut erklärt. http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS01/F2/Files/uvw-web-Dateien/uvw-web1.html RE: pumping lemma - georg - 15.07.2007 20:38
Anonymer User schrieb:
Das ist eine frei wählbare Zahl, für die gilt:
|w|>=n
Zitat:
Nehmen wir als Beispiel die Sprache a^m*b^2*c^m (m aus N)
Zitat:
Ein (einfaches)Wort aus der Sprache wäre: a^n*b^2*c^n (n aus N)
|w|= n +2 +n =2n +2 >= n(Pumping-Länge) Du könntest auch 2n als Pumping-Länge nehmen oder n/2 oder sogar 2n+2.
Zitat:
Ein anderes Beispiel: a^2*b^3*c^4 es gibt also keine Variablen, somit wird die Sprache von einem einzigen Wort gebildet.
|w|=2+3+4=9 Ich wähle mir als P-Länge (n=)2
Zitat:
1.|uv|>= 1
2. |v| größer Null 3. für ein beliebiges i aus N muss u*v^i*w aus der Sprache sein.Wenn ich als i 100 wähle, dann ist ein so gebildetes Wort nicht drin. Wenn eine Sprache von einem einzigen Wort gebildet wird, dann muss man so einen Widerspruchsbeweis erst gar nicht aufstellen, weil es offensichlich ist.
Zitat:
Ich wollte dir aber mit diesem besonderen Beispiel zeigen, dass die Pumping-Länge auch eine Zahl sein kann-wenngleich selten.
RE: pumping lemma - Anonymer User - 08.10.2007 10:38 irgendwie bin ich grad total dumm glaub ich,wo ist mein denkfehler? -Das Pumping Lemma ist notwendig für Reguläre Sprachen. -Reguläre Sprachen werden durch Typ3 Grammatiken erzeugt und können durch Reguläre Ausdrücke dargestellt werden. Wenn man jetzt z.B. das Alphabet = {a} hat, dann ist {a} ein regulärer Ausdruck, die Produktionsregel wäre also: {S -> a}. und das einzige Wort das diese Sprache hat ist w = a. aber diese Sprache erfüllt doch nicht das Pumping Lemma, aber wenn das doch notwendig ist?! RE: pumping lemma - UncleOwen - 08.10.2007 13:21 Doch, die Sprache erfuellt das Pumping-Lemma. Mit Pumpinglaenge 2 gibt es einfach kein w, das die geforderte Laenge hat - und damit ist der Rest automatisch erfuellt. RE: pumping lemma - Anonymer User - 08.10.2007 18:59 Wie sieht das für die Sprache: L = { a^i b^j | i < j } Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar? Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert. RE: pumping lemma - georg - 08.10.2007 20:12
Anonymer User schrieb:
Wie sieht das für die Sprache:
L = { a^i b^j | i < j } Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar?
Zitat:
Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert.
RE: pumping lemma - theorinix - 09.10.2007 17:47
georg schrieb:
Anonymer User schrieb:
Wie sieht das für die Sprache:
L = { a^i b^j | i < j } Wäre das ein Beispiel für eine Sprache die nicht regulär ist und trotzdem pumpbar?
Zitat:
Ich habe zumindest keine Zerlegung gefunden, die das Wort aus L katapultiert.
RE: pumping lemma - georg - 09.10.2007 18:51
theorinix schrieb:
Würde in solch einer Zerlegung das Wort v die Form v=b^{s} (0<s<n) besitzen, so wäre das Wort uw nicht mehr in L, denn das wäre doch v=a^{n}b^{n+1-s}, mit n+1-s=<n.
|