[FoSAP] Kleeneabschluss

[Snoopy]

Wir fragen uns hier gerade beim Lernen wie der Kleeneabschluss richtig konstruiert wird, und zwar geht es um die Epsilon-Transition, die vom Endzustand zum Startzustand geführt wird. Uns scheint klar, dass äquivalent ist die Transition vom alten Endzustand zum alten Startzustand zu führen oder vom neuen Endzustand zum neuen Startzustand.

In der Vorlesung war ersteres definiert worden, in der Globalübung Prinzip zwei. Was sollen wir denn machen? Gibt es da etwas zu bevorzugen?

[CrazyPumuckl]

was immer gehen sollte, ist, wenn du den Kleeneabschluss wie in der Thompsonkonstruktion wählst.

[oxygen]

Wir fragen uns hier gerade beim Lernen wie der Kleeneabschluss richtig konstruiert wird, und zwar geht es um die Epsilon-Transition, die vom Endzustand zum Startzustand geführt wird. Uns scheint klar, dass äquivalent ist die Transition vom alten Endzustand zum alten Startzustand zu führen oder vom neuen Endzustand zum neuen Startzustand.

In der Vorlesung war ersteres definiert worden, in der Globalübung Prinzip zwei. Was sollen wir denn machen? Gibt es da etwas zu bevorzugen?

Ich denke ersteres. Bei der 2. Variante hat man ja einen Zyklus aus e-Transistionen was irgendwie... hässlich ist.

[Commo]

Wenn ich mich recht erinnere, habe ich es in der Probeklausur so gemacht, dass ich einen neuen Startzustand vor dem alten eingeführt habe und vom alten Endzustand zum neuen Startzustand eine Transition, den neuen Startzustand als Endzustand.

Das ist definitiv falsch! (Auch, wenn der Automat die gleiche Sprache beschreibt)

Ich meine es war genau andersherum, dass man einen neuen Endzustand rechts macht, dann vom alten Startzustand zu dem (kein mal) und vom neuen Endzustand zum alten Startzustand (beliebig oft). (Auch, wenn das etwas hässlicher aussieht als meine Variante)

[mirko]

du machst einen neuen startzustand (im weiteren als S' bezeichnet) UND einen neuen endzustand (F'). dann ne €-transition von S' nach S (alter startzustand), eine von F nach F', eine von S' nach F' und eine von F nach S.

am besten malst du dir das auf, und merkst dir das bild

[Der_Baz]

du machst einen neuen startzustand (im weiteren als S' bezeichnet) UND einen neuen endzustand (F'). dann ne €-transition von S' nach S (alter startzustand), eine von F nach F', eine von S' nach F' und eine von F nach S.

am besten malst du dir das auf, und merkst dir das bild

genau so würde ich das auch machen

[foogy]

du machst einen neuen startzustand (im weiteren als S' bezeichnet) UND einen neuen endzustand (F'). dann ne €-transition von S' nach S (alter startzustand), eine von F nach F', eine von S' nach F' und eine von F nach S.

am besten malst du dir das auf, und merkst dir das bild

Das wäre ja exakt die Konstruktion nach Thompson. In meiner Vorlesungsmitschrift steht das ein klein wenig anders drin. Und zwar genau so wie du beschrieben hast, nur dass anstelle von "eine von S' nach F' und eine von F nach S" hier zwei epsilon-Transitionen zwischen S' und F' gezeichnet wurden, eben eine in jede Richtung. Kann das noch wer bestätigen? Glaube nicht, dass ich falsch abgezeichnet UND falsch abgeschrieben habe.

[mirko]

du machst einen neuen startzustand (im weiteren als S' bezeichnet) UND einen neuen endzustand (F'). dann ne €-transition von S' nach S (alter startzustand), eine von F nach F', eine von S' nach F' und eine von F nach S.

am besten malst du dir das auf, und merkst dir das bild

Das wäre ja exakt die Konstruktion nach Thompson. In meiner Vorlesungsmitschrift steht das ein klein wenig anders drin. Und zwar genau so wie du beschrieben hast, nur dass anstelle von "eine von S' nach F' und eine von F nach S" hier zwei epsilon-Transitionen zwischen S' und F' gezeichnet wurden, eben eine in jede Richtung. Kann das noch wer bestätigen? Glaube nicht, dass ich falsch abgezeichnet UND falsch abgeschrieben habe.

ich kenne für den kleene-abschluss nur die verfahren nach thompson und gluschkow - die haben wir auf jeden fall in der vl gemacht - ein anderes verfahren ist mir nicht bekannt...

[mgla]

ich kenne für den kleene-abschluss nur die verfahren nach thompson und gluschkow - die haben wir auf jeden fall in der vl gemacht - ein anderes verfahren ist mir nicht bekannt...

Jep, machts lieber so. Alle die das in der Präsenzübung nicht so gemacht haben - und die Aufgabe dazu war sehr simpel - haben keine Punkte bekommen.

[MartinM]

ich kenne für den kleene-abschluss nur die verfahren nach thompson und gluschkow - die haben wir auf jeden fall in der vl gemacht - ein anderes verfahren ist mir nicht bekannt...

Jep, machts lieber so. Alle die das in der Präsenzübung nicht so gemacht haben - und die Aufgabe dazu war sehr simpel - haben keine Punkte bekommen.

Wundert mich. Ist eigentlich ein Unding. A* ist A* ist A* und in der Aufgabenstellung war nichts von Glushkov gefordert...

[maddinac]

Eigentlich kann ich das doch machen wie ich lustig bin, solange es richtig ist.
Wenn nichts von Thompson oder Gluskov in der AUfgabe steht können die mir dann nix.

[mirko]

Eigentlich kann ich das doch machen wie ich lustig bin, solange es richtig ist.
Wenn nichts von Thompson oder Gluskov in der AUfgabe steht können die mir dann nix.

auf dem titelblatt stand aber (sinngemäß): "benutzen sie die verfahren aus der vl". ich gehe davon aus, dass das auch bei der klausur draufstehen wird, und somit dann für alle aufgaben gilt...

[MartinR]

In der VL vom 26.4. haben wir bevor Thompson behandelt wurde, als über Abschlusseigenschaften regulärer Sprachen gesprochen wurde, eine Konstruktion für einen kleene-verabgeschlossenen Automaten behandelt. Funktioniert aber genau wie thompson, nur dass der Ausgangsautomat halt im Gegensatz zu einem Thompson-kontruierten mehrere Start- und Endzustände haben könnte. Also:
- alte Start- und Endzustände sind keine Start- bzw. Endzustände mehr
- neuer Startzustand, neuer Endzustand
- eps-Übergänge
von neuem Startzustand zu allen alten Startzuständen
von allen alten Endzuständen zum neuen Endzustand
von allen alten Endzuständen zu allen alten Startzuständen
vom neuen Startzustand zum neuen Endzustand.

Glaube nicht, dass ich falsch abgezeichnet UND falsch abgeschrieben habe.

Ich fürchte doch

[dnjansen]

Es gibt mehrere ähnliche Verfahren, die alle eine Art Kleene-Abschluss erzeugen.

Das Thompson-Verfahren ist, was mirko geschrieben hat.

Ich habe daneben noch ein Verfahren vorgeführt, das gemeint war, um aus einem beliebigen NEA einen epsilon-erweiterten NEA zu machen, der den Kleeneabschluss des ersten erkennt. Das ist, was im Beitrag von foogy steht.

An MartinR's Konstruktion kann ich mich nicht mehr erinnern (oder kommt das nur weil es für mich schon zu spät abends ist?). Das ist eine Art Mittelding zwischen den beiden. Bei einem Thompson-Automaten (d.i. ein NEA, der durch Thompson-Konstruktion entstehen kann) wirkt es genau wie die Thompson-Konstruktion; aber wenn ein Automat mehrere Start- oder Endzustände hat, bekommt der Kleeneabschluss nach MartinR mehr Transitionen als der nach foogy.

Lernen Sie auf jeden Fall die Thompson-Konstruktion (und natürlich Gluschkow).

[foogy]

Lernen Sie auf jeden Fall die Thompson-Konstruktion (und natürlich Gluschkow).

Danke für die ausführliche Erläuterung.
Sollte also wo nach dem Kleeneschen Abschluss gefragt sein, sind wir also mit Thompson auf der sicheren Seite.