infostudium.de

von **CrazyPumuckl** » 02.08.07 17:44

Hab noch ne Frage zum PL

(hier am Bsp für reguläre Sprachen)

z.Z.: $a^{n} b^{n}$ nicht regulär.

Sei n die PL-Konstante.

Meine Idee war folgende.: |uv| <= n, |v| >= 1
=> uv besteht nur aus a's.

bilde $uv^{2}w$ . Da |uvw| = n+n = 2n ist, gilt:
$|uv^{2}w|$ = |uvw| + |v| >= 2n + 1.

Meine Frage jetzt: Reicht das als Widerspruch? Die Wörter aus der Sprache müssen ja eine gerade Anzahl an Buchstaben haben. Ich habe einfach v = 1 gesetzt. Daher gibt es ein Wort, dass 2n+1 Zeichen hat. (und das ist ungerade). Reicht es also, ein Gegenbeispiel zu finden, oder muss ich zeigen, dass das für jede Wahl von v zum Widerspruch führt? Wenn man ja z.B. v = 2 setzt kann ich so nicht nen Widerspruch erzeugen.

Thx.

von **Fighter_MV** » 02.08.07 17:51

Du musst EIN Wort finden, mit dem du arbeitest.

Für dieses Wort musst du für ALLE Möglichkeiten die es gibt u, v und w zu wählen einen Widerspruch finden.

Bis zu dem Punkt wo du sagt uv besteht nur aus a's, hast du schon bewiesen, dass die Sprache nicht regulär ist.

Denn egal wie du v wählst, es wird immer nur a's enthalten und somit werden in dein neues Wort nur a's hinzugefügt womit die Bedingung verletzt wird, dass genau soviele a's wie b's in der Sprache enthalten sein müssen.

von **CrazyPumuckl** » 02.08.07 17:56

ja, das ist mir klar. ich kann das nur nie so formal formulieren. in einem text schon, aber ich glaube nicht, dass die das dann akzeptieren, daher hab ich nach was formalem gesucht

von **Fighter_MV** » 02.08.07 18:16

|uv| <= n, |v| >= 1

=> uv besteht nur aus a's.

Laut Pumping Lemma muss gelten:

$uv^xw \in L(G) \forall x \in N$

Da v nur aus a's besteht gilt:

=> |a| > |b| $\forall x \in N$

=> $uv^xw \notin L(G)$

oder so ähnlich halt

von **Muffi** » 02.08.07 19:05

Die Behauptung ist doch, dass _ein_ n ex., so dass es für _alle_ Wörter länger als n _eine_ Zerlegung gibt, bla bla.

Sprich: Du beginnst immer so:

Angenommen, L sei regulär. Sei n beliebig, aber fest (um das erste "ein" abzuhaken). Danach suchst du dir ein Wort, mit den du die Behauptung zum Widerspruch führen möchtest. Denn ein Gegenbeispiel reicht ja schon aus, um das "alle" zu widerlegen. Klugerweise wählst du dein Wort aus der Sprache in Abhängigkeit von der Punping-Konstante. Das n in der Definition der Sprache hat grundsätzlich nämlich nichts mit der Pumping-Konstante zu tun. Dass beide "n" heißen, ist Zufall. Wählen wir hier also $a^nb^n$ . Wenn aber für Teil 3 (das zweite "ein") eine Zerlegung nicht funktioniert, heißt das noch lange nicht, dass es keine funktionierende gibt.
Jetzt musst du zeigen, dass es tatsächlich keine Zerlegung geben kann: Wegen $|uv|\leq n$ muss in jeder (!) Zerlegung das v aus lauter a bestehen. Nun kannst du zeigen, dass $uv^2w$ nicht aus der Sprache ist, weil zu viele a aufeinanderfolgen. Da jedes v die Anzahl der a erhöht, die der b aber nicht, ist $uv^2w$ nicht in der Sprache, was einen Widerspruch zur Voraussetzung ist. Damit ist alles gezeigt.

von **Commo** » 04.08.07 13:24

Ja genau, nur um es nochmal fest zu halten, dass das wesentliche die Punkte sind "für alle n, n dann fest" und für alle Zerlegungen "uv". In dem Beispiel kann ja v = a oder v = aa, etc. sein, aber alles läuft darauf hinaus, dass es zu viele a's werden, wenn die mit der Pumping-Konstante aufgepumpt werden.

von **der-cain** » 04.08.07 16:09

Muffi hat geschrieben: [...] Das n in der Definition der Sprache hat grundsätzlich nämlich nichts mit der Pumping-Konstante zu tun. Dass beide "n" heißen, ist Zufall. [...]

Das sehe ich anders, denn erstens gilt n = n (formal) und zweitens würde das ganze lemma keinen sinn machen, denn wenn das n in $a^{n}b^{n}$ kleiner als das n im Pumping-Lemma wäre, dann könnte man wieder eine Zerteilung finden, wo das Wort in der Sprache liegt.

von **MartinR** » 04.08.07 17:21

der-cain hat geschrieben:
Muffi hat geschrieben: [...] Das n in der Definition der Sprache hat grundsätzlich nämlich nichts mit der Pumping-Konstante zu tun. Dass beide "n" heißen, ist Zufall. [...]

Das sehe ich anders, denn erstens gilt n = n (formal) und zweitens würde das ganze lemma keinen sinn machen, denn wenn das n in $a^{n}b^{n}$ kleiner als das n im Pumping-Lemma wäre, dann könnte man wieder eine Zerteilung finden, wo das Wort in der Sprache liegt.

Das ist so falsch, dass ich gar nicht weiß, wie ich das berichtigen soll :shock:

Nur mal so, dir ist schon klar, dass die das PL sagt, dass es ein k gibt (huch, ich hab es k genannt!), so dass für alle Wörter in L länger als k gilt: blaaaah.
und weil es für jedes k in $a^{n}b^{n}$ offensichtlich Wörter gibt, die länger als k sind, macht das ganze Lemma doch irgendwie Sinn, oder?

EDIT: Vielleicht bist du auch einfach durcheinander und hast übersehen, dass du dir das Wort aussuchen darfst im Gegenbeweis? Dann ein Wort zu wählen, das kürzer als die Pumpingkonstante ist, ist natürlich grober Unfug.

von **Teq** » 04.08.07 18:06

Mal kurz eine Frage eingeworfen zur Aufgabe 7.3.d) Seite 313 im Buch.
L ist die Sprache, in der a, b, c gleichoftvorkommen.

Wenn ich mich auf ein Gegenbeispiel einschränken kann, reichts doch
$z = a^nb^nc^n$ zu wählen, und dann das PL wie im Beispiel im Buch (S. 295) durchzuführen, oder? Das wäre dann deutlich einfacher geworden...

von **dnjansen** » 04.08.07 23:35

der-cain hat geschrieben:
Muffi hat geschrieben: [...] Das n in der Definition der Sprache hat grundsätzlich nämlich nichts mit der Pumping-Konstante zu tun. Dass beide "n" heißen, ist Zufall. [...]

Das sehe ich anders...

Muffi hat's begriffen.
Die Sprache ist eigentlich $\{ a^nb^n \mid n \in N \}$ , und das ist dasselbe wie $\{ a^xb^x \mid x \in N \}$ und wie $\{ a^mb^m \mid m \in N \}$ usw., weil das n in dieser Formel gebunden ist (d.h. sozusagen von aussen unsichtbar).

@Teq: Geht es in der Aufgabe wirklich um das PL für reguläre Sprachen, oder eher um das für kontextfreie? Das Gegenbeispiel ist in beiden Fällen brauchbar, aber man muss je nachdem verschieden weiterfahren.

von **nomawie** » 04.08.07 23:57

Mal eine andere Frage: Was ist $a^{n^2}$

1. $(a^n)^2$ oder
2. $a^{(n^2)}$

von **Tim** » 05.08.07 00:07

es kann eigentlich nur zweites sein, weil ersteres ja a^2*n wäre

von **mirko** » 05.08.07 00:09

nomawie hat geschrieben:Mal eine andere Frage: Was ist $a^{n^2}$

1. $(a^n)^2$ oder
2. $a^{(n^2)}$

wäre der erste fall gemeint, würde da wohl $a^{2n}$ stehen...

von **Commo** » 05.08.07 13:04

der-cain hat geschrieben:Das sehe ich anders, denn erstens gilt n = n (formal) und zweitens würde das ganze lemma keinen sinn machen, denn wenn das n in $a^{n}b^{n}$ kleiner als das n im Pumping-Lemma wäre, dann könnte man wieder eine Zerteilung finden, wo das Wort in der Sprache liegt.

Ne, du musst das als zwei verschiedene n Werten, aber der Punkt ist einfach, dass du in der zweiten Bedingung des Pumping-Lemmas folgendes haben musst: $\left|uv\right| \leq n$ . Du kannst da z.B. die Zerlegung
$a^{n-2}b^{2}$
wählen, aber dadurch machst du es dir nur schwer, denn da gesagt wird "es existiert _eine_ Zerlegung uv" steht nicht fest, was u und was v in dem Term ist. Dadurch müsstest du später die Fälle unterscheiden, wo u nur aus a besteht, u aus a und b.

Einfacher kannst du es dir machen, wenn du die Zerlegung so wählst $uv = a^n$ . Dann hast du nämlich nur den Fall, dass u und v beide aus a bestehen. Bei der dritten Aussage des P-Lemmas $uv^iw \in L$ kannst du damit auch sofort sagen, dass der Term $uv^i$ nur um a wächst und zwar kommen i-stück hinzu. Dann ergibt sich der Widerspruch.

Es ist also am bequemsten, wenn du dort, wo Exponenten im Term der Sprache stehen n einsetzt, und dann sieht der Term unter Umständen genauso aus, wie der eigentliche Term. Aber der erste Ansatz, den ich gesagt habe, wäre genauso richtig, nur komplizierter.

Eigentlich verwirrt das manchmal auch nur, dass man sich an das n hält. Gab mal so ein Beispiel, wo der Term $a^mba^n \ldots$ war und da ist es am besten, wenn du m=k setzt und dich um das andere n nicht mehr kümmerst, das muss nämlich nicht zwangsläufig auch n=k sein, sondern kann irgendwas anderes sein. Ich such mal das Beispiel und rechne die Aufgabe vor.

*EDIT*
Da: http://www.majorgames.de/uni/atfs/FSAP-Pumping_Lemma_Typ_3.pdf

von **der-cain** » 05.08.07 15:54

Was ich mit meiner Aussage meinte, ist natürlich das n (bzw. k) in dem selbstgewählten Wort und nicht das n der Definition der Sprache. Tut mir Leid, da bin ich wohl über meine eigenen Füße gestolpert...

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[FoSAP] Pumping Lemma

Pumping Lemma