Einige Fragen...

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Einige Fragen...

Beitrag von kain » 25. Aug 2010 16:21

Hallo,

ich bitte um eure Hilfe. Es geht um folgendes:

1. Minimalautomat
2. Pumping-Lemma

Zu 1:

1. der Autmatentyp ist doch egal oder? DFA oder NFA?
2. Vorgehensweise: Zustandsäquivalenz, das heisst, ich trenne zwischen den akzeptierenden und nichtakzeptierenden Zuständen. Jetzt habe ich zwei Gruppen. Wie geht es jetzt weiter mit Zustandsäquivalen/Wortäquivalenz?

Zu 2:

Man benutzt das Pumping-Lemma um die Nicht-Regularität zu zeigen, aber wie geht man hier genau vor?
Was ich nicht so ganz verstehe ist folgendes:

Man überprüft immer ob es u, v, w geben kann. Ein Teil der bedingungen ist, dass es einmal ein v mit |v| > 0 gibt und es soll auch gelten, dass
uw Element L mit m = 0.

Hier komm ich schon durcheinander. Einmal ein |v| > 0 und einmal ein v^m mit m = 0 => uw Element L.

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Einige Fragen...

Beitrag von franzose » 26. Aug 2010 02:15

zu 1)

wir haben es nur für DFAs gemacht. du baust quasi einen Automaten, der nur genausoviele Äquivalenzklassen hat, die er benötigt. Am Anfang trennen zwischen Akzeptierend/Nicht-Akzeptierend.

Jetzt für jede mögliche Transition schauen, ob du nochmal in weitere Äquivalenzklassen unterteilen muss (z.B. wenn ein akzeptierender Zustand bei einer Transition wieder in einen akzeptierenden Zustand kommt und ein anderer akzeptierender Zustand bei der selben Transition in einen nicht zkzeptierenden Zustand wechselt dann sind die nicht äquivalent).

das muss man so lange machen, bis sich nix mehr ändert (also bis man die benötigte Anzahl an verschieden Äquivalenzklassen hat, siehe Myhill-Nerode)

zu 2)

ich gehe mal davon aus du betrachtest das Pumping-Lemma für reguläre Sprachen. Es sagt dass bei jeder regulären Sprache ab einer gewissen Wortlänge n jedes größere Wort sich zerlegen lässt in uvw (mit nicht leerem v und Länge von uv kleiner n) sodass man das v "pumpen" kann (also beliebig wiederholen oder weglassen kann).

triviales Beispiel: die Sprache von dem REG: aba*ba lässt sich für alle Wörter länger als 5 zerlegen mit u=ab und v=a (und w=a*ba) dann kannst du immer das v (also das mittlere a) pumpen.

wie du aber richtig erkannt hast, ist das pumping-lemma nur eine notwendige Bedingung: jede reguläre Sprache muss es erfüllen (also wenn du es erfüllst kann man nix sagen, aber wenn du es nicht erfüllst, dann bist du KEINESWEGS regulär)

so kann man z.B. zeigen, dass a^n b^n nicht regulär ist. alle Wörter größer einem n kann ich nicht wie beschrieben zerlegen, da in dem uv-Teil (maximal so lang wie n) nur a auftauchen, wenn ich die dann pumpe, dann habe ich nicht mehr die gleiche Anzahl von a und b.


ich habe leider nicht ganz verstanden was du meinst, ich hatte aber das Gefühl das du da ziemlich was durcheinander gebracht hast. vll. hilft es dir mit der Beschreibung wirklich zu verstehen, was das pumping-lemma aussagt.

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Einige Fragen...

Beitrag von JanM » 26. Aug 2010 09:58

Zu 2)
1. es wird ein beliebiges n\(\in \mathbb{N}\) gewählt.
2. jetzt bist du dran dir ein x\(\in\)L auszuwählen. Das solltest du möglichst geschickt wählen. Das bedeutet du schaust wo hat L den "Schwachpunkt". Zum Beispiel hat die Sprache \(a^{n}b^{n}\) den Schwachpunkt, dass sie genausoviele a's wie b's enthalten muss. Man wählt x=\(a^{n}b^{n}\). Das Wort ist in der Sprache und länger als n. Wie die Schwachstelle ausgenutzt wird mit diesem Wort siehe weiter.
3. Nun wird eine Zerlegung von x in uvw vorgenommen. Diese darfst du auf KEINEN FALL wählen. Du kannst nur indirekt darauf schließen, da die Zerlegung die Bedingungen |uv| \(\le\)n, und v\(\not= \epsilon\) erfüllen muss.
Bei unserem Wort \(a^{n}b^{n}\) bedeutet das, dass der Anfangsabschnitt uv nur a's enthält, da das Wort x mit n a's beginnt ( \(a^n\) ). Da v nicht das leere Wort sein darf muss es mindestens 1 a enthalten und darf aber kein b enthalten, da uv ja bereits nur a's enthält.
4. Jetzt bist du wieder am Zug. Du darfst den Abschnitt v so oft "pumpen" wie du möchtest. Jetzt kannst du, da das Wort geschickt gewählt wurde die Schwachstelle der Sprache ausnutzen. Du weißt, dass v nur aus a's besteht und du nun also so viele a's wie du möchtest erzeugen kannst, indem du v beliebig oft "pumpst". Zum Beispiel kannst du m = 10 wählen. Du weißt zwar nicht genau wie viele a's der Abschnitt v enthält. Aber das musst du auch nicht. Alles was du wissen musst ist, dass v mindestens ein a enthält. Und wenn du dieses 1 a nun 10 mal pumpst erhälst du das Wort \(a^{n+10}b^n\), was nicht mehr in der Sprache ist, da es mehr a's als b's enthält.
Du könntest auch m=0 wählen und pumpst somit 0 mal(nimmst also den Abschnitt v aus dem Wort x heraus). wenn wir immer noch annehmen, dass v 1 a enthält, dann entsteht das Wort \(a^{n-1}b^n\) was auch nicht mehr in der Sprache ist.
im allgemeinen nimmst du aber an, dass v von der Form \(a^{k}\) ist (also k viele a's enthält). Dann gilt für beispielsweise m=0, dass das Wort \(a^{n-k}b^n\) entsteht, da du ja k viele a's aus x herausnimmst.

Hoffe das hat es etwas verständlicher gemacht.
Aber ich kann franzose nur zustimmen, dass deine Frage etwas schwammig formuliert war.

mithrawnuruodo
Erstie
Erstie
Beiträge: 22
Registriert: 4. Sep 2009 00:03

Re: Einige Fragen...

Beitrag von mithrawnuruodo » 27. Aug 2010 18:24

Hallo ich hoffe ich verwirre den eigentlichen Fragenden mit meiner weiteren Frage nicht. Also es hieß ja ich darf die Zerlegung auf keinen Fall wählen oder ? Ich hatte mich nämlich zum Pumping lemma gefragt gilt es für "eine" Zerlegung oder für alle möglichen Zerlegungen. Wenn letzteres der fall wäre könnte man ja zeigen das es keine Reguläre Sprache ist indem man eine Zerlegung findet unter der das Pumpinglemma für die entsprechende Sprache nicht efüllt ist, was sich irgendwie auch sinnvoll angehört hat. Aber wenn man wirklich die Zerlegung nicht wählen darf wäre der Nachweis von irregularität mit dem Pumpinglemma ja gleich ein ganzes Stück schwerer von daher ..... warum darf man die Zerlegung nicht wählen .... *confused*

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Einige Fragen...

Beitrag von franzose » 27. Aug 2010 22:15

ich glaube gemeint war, dass es beim pumping lemma wenigstens EINE Zerlegung geben muss. D.h. du musst beim Nachweis von nicht-Regularität zeigen, dass es KEINE einzige Zerlegung gibt. Also genügt es nicht eine Zerlegung anzugeben, bei der es nicht klappt. Ähnlich wie beim Semantik-Spiel darfst du also keine konkrete auswählen, sondern musst allgemein zeigen, dass es keine mögliche Zerlegung gibt.


Bitte korrigieren, wenn ich falsch liege/nicht kapier habe worum es geht....

Vladimir
Neuling
Neuling
Beiträge: 10
Registriert: 18. Apr 2010 11:43

Re: Einige Fragen...

Beitrag von Vladimir » 1. Sep 2010 10:45

Klausur zu FGdI (2005-06) Aufgabe 3 (zum Pumping Lemma)

\(L_1 = \{ a^nb^ka^nb^k : n,k \in N\}\) - nicht kontextfrei, nicht regulär
  • \(x=uvw;\)
    \(u=a^n;\)
    \(v=b^k;\)
    \(w=a^nb^k;\)
    \(x=uv^mw; \to\) nicht in der Sprache, nicht regulär

    \(x=yuvwz;\)
    \(y=a^n;\)
    \(u=b^k;\)
    \(v=a^n;\)
    \(w=b;\)
    \(z=b^{k-1};\)
    \(x=yu^mvw^mz; \to\) nicht in der Sprache, nicht kontextfrei
\(L_2 = \{ a^nb^ka^kb^n : n,k \in N\}\) - nicht kontextfrei, nicht regulär
  • \(x=uvw; u=a^n; v=b^k; w=a^kb^n;\)
    \(x=uv^mw; \to\) nicht in der Sprache, nicht regulär

    \(x=yuvwz; y=a^n; u=b^k; v=a^k; w=b; z=b^{n-1};\)
    \(x=yu^mvw^mz; \to\) nicht in der Sprache, nicht kontextfrei
\(L_3 = \{ a^nb^na^kb^k : n,k \in N\}\) - nicht kontextfrei, nicht regulär
  • \(x=uvw; u=a^n; v=b^n; w=a^kb^k;\)
    \(x=uv^mw; \to\) nicht in der Sprache, nicht regulär

    \(x=yuvwz; y=a^n; u=b^n; v=a^k; w=b; z=b^{k-1};\)
    \(x=yu^mvw^mz; \to\) nicht in der Sprache, nicht kontextfrei
Was mache ich falsch?

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Einige Fragen...

Beitrag von franzose » 1. Sep 2010 15:06

ganz allgemein ist dein Ansatz falsch, eine konkrete Zerlegung anzugeben bei der es nicht klappt, sondern man muss zeigen, dass es GAR KEINE mögliche Zerlegung gibt für Wörter länger als n


Erinnerung: wenn L regulär, dann EXISTIERT ein n, sodass FÜR ALLE längeren Wörter EXISTIERT (wenigstens) EINE Zerlegung, sodass man pumpen kann.

Nicht-Regularität lässt sich also nicht beweisen, indem man zeigt: es gibt KEIN n, sodass bei allen längeren Wörtern eine solche Zerlegung existiert. Also FÜR ALLE möglichen n EXISTIERT (wenigstens) ein längeres Wort, bei dem FÜR ALLE Zerlegungen sich das Wort nicht pumpen lässt

die Quantoren werden umgedreht

(bei dem pumping lemma für kontextfrei ist es genauso)


schau mal hier im Forum, zum pumping lemma gibt es schon ziemlich viele Beiträge....

Vladimir
Neuling
Neuling
Beiträge: 10
Registriert: 18. Apr 2010 11:43

Re: Einige Fragen...

Beitrag von Vladimir » 2. Sep 2010 09:13

hi franzose, vielen Dank, jetzt habe ich das verstanden)

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Einige Fragen...

Beitrag von patrix » 2. Sep 2010 11:55

Hi franzose, vladimir hat aber doch mit seiner Annahme recht, dass keine der drei Sprachen kontextfrei und somit auch nicht regulär ist oder? (Wenn auch falsch bewiesen)

Grüße Patrick

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Einige Fragen...

Beitrag von bruse » 2. Sep 2010 12:04

Die unteren beiden sind kontextfrei, aber nicht regulär. Entsprechende Grammatiken sind auch gar nicht so kompliziert.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Einige Fragen...

Beitrag von patrix » 2. Sep 2010 12:37

ja natürlich mit einem Kellerspeicher auch lösbar jetzt seh ich es!

vielen Dank (mal wieder)

Vladimir
Neuling
Neuling
Beiträge: 10
Registriert: 18. Apr 2010 11:43

Re: Einige Fragen...

Beitrag von Vladimir » 2. Sep 2010 16:31

\(L_1 = \{ a^nb^ka^nb^k : n,k \in N\}\) - nicht kontextfrei, nicht regulär

\(L_2 = \{ a^nb^ka^kb^n : n,k \in N\}\) - regulär (und kontextfrei)
\(x=uvw; u=a^n; v=b^ka^k; w=b^n;\)
\(uv^mw; \to\) in der Sprache, regulär

\(X \to aXb|aYb\)
\(Y \to bYa|e\)

\(L_3 = \{ a^nb^na^kb^k : n,k \in N\}\) - kontextfrei, nicht regulär
\(x=uvw; u=a^n; v=b^n; w=a^kb^k;\)
\(uv^mw; \to\) nicht in der Sprache, nicht regulär

\(x=yuvwz; y=a^{n-1}; u=a; v=b^{n-1}; w=b; z=a^kb^k;\)
\(yu^mvw^mz; \to\) in der Sprache, kontextfrei

\(X \to YY\)
\(Y \to aYb\)

Oder?

jls
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 18. Okt 2009 13:02

Re: Einige Fragen...

Beitrag von jls » 2. Sep 2010 17:13

zu L2: sei \(n\) die PL- Zahl, betrachten wir das Wort \(a^nb^{2n}a^{2n}b^n\) (Länge \(6n\), in der Sprache enthalten)
dann besteht wegen \(|uv| \le n\) und \(|v| > 0\) \(v\) nur aus \(a\)'s, wir können \(v\) beispielsweise "auf 2 pumpen" (weil \(u v^i w\) für alle \(i = 0,1,2,..\) in der Sprache erhalten sein muss, also z.B. auch \(u v^2 w\), 3. Bedingung des PL) und erhalten dann zuviele \(a\) am anfang des Wortes, womit das Wort nicht mehr in der Sprache liegt --> nicht regulär.

Jetzt vielleicht nicht so elegant formuliert, aber stimmt das in etwa?

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Einige Fragen...

Beitrag von JanM » 2. Sep 2010 18:45

Das Ding ist, dass du zwar eine Grammatik angegeben hast, die die Sprache erzeugt, allerdings ist diese Grammatik nicht regulär.
Eine reguläre Grammatik hat nur rechtslineare Produktionen (Skript S.49) und X -> aXb ist nicht rechtslinear.

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Einige Fragen...

Beitrag von franzose » 2. Sep 2010 23:42

nur weil man eine kontextfreie Grammatik angibt, heißt das im Allgemeinen nicht, dass es nicht regulär ist (es könnte auch eine reguläre äquivalente Grammatik geben)

in diesem konkreten Fall natürlich nicht....

Antworten

Zurück zu „Archiv“