infostudium.de

von **foogy** » 07.08.07 20:58

Also mal zu dem Verfahren der Vereinigung:

Formal gilt: $L(A) \cup L(B) = \overline{\overline{L(A)}\cap \overline{ L(B)}} = \overline{\overline{A}\times \overline{B}}$

Das ist natürlich unheimlich viel Arbeit. In meiner Übung (oder war's ne VL, oder GÜ? oder gar das Buch?) habe ich mir aber aufgeschrieben: In der Praxis arbeitet man nicht mit dem Komplementautomaten, sondern bildet den Produktautomaten $A \times B$ , mit folgender Endzustandsmenge: $F = \{<q_A,q_B> | q_A \in F_A \text{ ODER } q_B \in F_B\}$
Man nimmt also den Produktautomaten aus Teil (b) und fügt noch ein paar Endzustände hinzu. Da ich nicht mehr weiß, wo ich das Verfahren her habe, wird das wohl für Diskussionsstoff in der Einsicht sorgen :-/

Im Übrigen fand ich 10 Punkte für A7 völlig überdimensioniert. Ich konnte sie z.B. nicht lösen, fand aber die Punktezahl gemessen am Aufwand (nach dem was man hier im Forum so liest) zu hoch. 5 Punkte wären wohl angemessen.

Ansonsten eine schöne Klausur. Habe für 90 Punkte bearbeitet, mal sehen was davon noch übrig bleibt. Kein Thomson, kein Glushkov? Skandalös!!
Der Kellerautomat war geschenkt. Das war übrigens keine reguläre Grammatik. Sie enthielt Regeln S -> aABA wenn ich mich recht entsinne.

Und was war bitte am Pumping-Lemma mit DIESER Sprache schwierig? Nimmt man sich halt als Wort $a^n b^n c^n$ , indem man sowohl i und j auf n setzt und somit max(i,j) = n ist. Dann reduziert sich die Arbeit auf eine der Beweise, die wir in den Übungen hatten. Oder habe ich hier was übersehen?

Bin erstmal offline... NetCologne hats vergeigt...

von **Anand** » 07.08.07 21:08

[quote="foogy"]Also mal zu dem Verfahren der Vereinigung:

Formal gilt: $L(A) \cup L(B) = \overline{\overline{L(A)}\cap \overline{ L(B)}} = \overline{\overline{A}\times \overline{B}}$

In der Praxis arbeitet man nicht mit dem Komplementautomaten, sondern bildet den Produktautomaten $A \times B$ , mit folgender Endzustandsmenge: $F = \{<q_A,q_B> | q_A \in F_A \text{ ODER } q_B \in F_B\}$
Man nimmt also den Produktautomaten aus Teil (b) und fügt noch ein paar Endzustände hinzu.

Genau so hab ichs gemacht!!

von **MartinR** » 07.08.07 21:25

foogy hat geschrieben:Und was war bitte am Pumping-Lemma mit DIESER Sprache schwierig? Nimmt man sich halt als Wort $a^n b^n c^n$ , indem man sowohl i und j auf n setzt und somit max(i,j) = n ist. Dann reduziert sich die Arbeit auf eine der Beweise, die wir in den Übungen hatten. Oder habe ich hier was übersehen?

Ja, hast du. Geb ich dir eine Zerlegung uvwxy, wo in v ein b und in x ein c ist hast du ein Problem.
Falsches Wort gewählt würd ich sagen.
Besser: $a^{n+1} b^n c^{n+1}$

von HE » 07.08.07 21:29

Wo ist denn da das Problem? Pumping Lemma macht eh nur immer Spaß für +1 oder -1. In dem Falle würdest du halt auf v und x ganz verzichten, dann gibt's noch n-1 'c's und noch n 'a's und alles ist puttputt.

von **Martin** » 07.08.07 21:40

HE hat geschrieben:Wo ist denn da das Problem? Pumping Lemma macht eh nur immer Spaß für +1 oder -1. In dem Falle würdest du halt auf v und x ganz verzichten, dann gibt's noch n-1 'c's und noch n 'a's und alles ist puttputt.

Genau. Doch richtiges Wort gewählt, würde ich sagen

von **nomawie** » 07.08.07 21:41

MartinR hat geschrieben:Ja, hast du. Geb ich dir eine Zerlegung uvwxy, wo in v ein b und in x ein c ist hast du ein Problem.
Falsches Wort gewählt würd ich sagen.

nö hat er nicht. dann darfst du nur nicht mit einem exponent größer 1 pumpen, sondern mit 0

von **MartinM** » 07.08.07 22:32

Raul hat geschrieben:Ich habe das angefangen und dann nach ~ 10 Zuständen abgebrochen, weil der Produktautomat zwischen den beiden vollständigen Komplementen echt riesig war! Nicht schwer, aber ich kann nicht glauben, dass das der Sinn der Aufgabe war.

Habe ich auch angefangen und habe aber schon nach 5 Zuständen abgebrochen, weil es 20 Zustände geworden wären und ich schon am Ende der Seite war...

Als 1. Idee habe ich die beiden Automaten nebeneinander geschrieben und behauptet es sei ein Automat mit 2 Startzuständen...

edit: Achso. Glushkov und Thompson soll dort gemeint gewesen sein?

von **foogy** » 07.08.07 22:35

nomawie hat geschrieben:nö hat er nicht. dann darfst du nur nicht mit einem exponent größer 1 pumpen, sondern mit 0

Ach scheisse. Naja, wenigstens Teilpunkte.

von **Commo** » 07.08.07 22:44

Genau mit 0 pumpen. Habe das so aufgeschrieben, dass entweder nur eine Buchstabenart gepumpt wird und ich sag mal jetzt ist die Variable p die Anzahl der Buchstaben, die hinzu kommt, dann sieht der Term so aus:
$a^{k+p}b^kc^k$ . Analog dazu die Terme $a^{k}b^{k+p}c^k, a^k b^k c^{k+p} |p>0$ .

Wenn v,x gemischt sind, dann wähle i=0 und es verschwinden immer p Buchstaben der einen Art und q Buchstaben der anderen Art. Die Terme sehen dann so aus: $a^{k-p}b^{k-q}c^k, a^kb^{k-p}q^{k-q} | p,q > 0$ .

von **Daniel** » 08.08.07 00:33

mit 0 pumpen geht aber genauso bei n, n+1, n+1. Ich habe die Wahl getroffen und es hat wunderbar funktioniert (genauso wie es auch mit n, n, n geht)

Das man gluskov machen sollte halte ich aber für ziemlich weit hergeholt. Dafür muss ich ja zuerst mal reguläre Ausdrücke bauen, und von der Negation war ja schon in Teilaufgabe 1 gesprochen worden.

Aber ok, das sehen wie ja hoffentlich bald

(an dnjansen: Bitte nicht böse werden, wenn sie meinen Produktautomaten aus der c sehen, der ist glaube ich nicht ganz einfach zu korrigieren

)

von **Martin** » 08.08.07 01:02

Daniel hat geschrieben:mit 0 pumpen geht aber genauso bei n, n+1, n+1. Ich habe die Wahl getroffen und es hat wunderbar funktioniert (genauso wie es auch mit n, n, n geht)

Sei $w = uvxyz$ die Zerlegung mit $v = b$ und $y = c$ .

$u v^0 x y^0 z = a^n b^n c^n \in L$

Für alle andern Potenzen klappt es natürlich auch...

von **Der_Baz** » 08.08.07 07:46

Raul hat geschrieben:Als 1. Idee habe ich die beiden Automaten nebeneinander geschrieben und behauptet es sei ein Automat mit 2 Startzuständen...

hab ich auch so, ist dann halt ein NEA.

und glushkov und thompson denke ich auch nicht, dass die gefordert waren.

von **foogy** » 08.08.07 07:56

Raul hat geschrieben:Als 1. Idee habe ich die beiden Automaten nebeneinander geschrieben und behauptet es sei ein Automat mit 2 Startzuständen...

Das entspricht genau der Methode im Buch. Sollte also in Ordnung sein. Wenn man jetzt noch nen neuen Startzustand mit je einer Epsilon-Transition zu allen alten Startzuständen dazubaut, dann hat man ja eigentlich das gleiche. In jedem Fall einen NEA. Letztere Möglichkeit steht irgendwo in meinen Mitschriften, und zwar BEVOR wir Glushkov oder Thompson hatten.

von **Fighter_MV** » 08.08.07 08:45

ich hab beim Pumpin Lemma

$a^{2n}b^nc^{2n}$

Dann hab ich 5 Fälle:

Nur a's pushen --> |a| > |c|

Nur b's pushen --> |b| > |a| aber |c| = |a|

Nur c's pushen --> |c| > |a| > |b|

a's und b's pushen --> |a| > |b| > |c|

b's und c's pushen --> |c| > |b| > |a|

--> nicht regulär

von **$veno** » 08.08.07 10:07

Ich hab beim Pumping Lemma folgende Zerlegung genommen:

$a^sb^nc^s (s>n, n PL-Konstante)$

Hab das PL also gleich für ne ganze Klasse von Funktionen damit widerlegt. Hat damit super funktioniert. Hab 9 Zerlegungen dabei raus:
1. vx= a..a
2. vx= b..b
3. vx= c..c
4. v = a..a x = b..b
5. v = a..ab..b x = b..b
6. v = a..a x = a..ab..b
7. v = b..b x = c..c
8. v = b..bc..c x = c..c
9. v = b..b X = b..bc..c

bei uv^iwx^iy kann man für alle Fälle außer den 2. Fall i = 0 wählen um das PL zu wiederlegen. für Fall 2 hab ich i = s+1 gewählt, das klappt dann auch.

Ist euer Transitionssystem auch so riesig? Ich hab da 17 Zustände und viele Transitionen kreuz und quer, ich hoffe die können dass noch vernünftig lesen!^^

Gruss Sven

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[FoSAP] After FSAP/AtfS - Ergebnisse on!