FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI-1: "Kleene's Konstruktion"

FGI-1: "Kleene's Konstruktion" 2011-04-15 15:53
Anonymer User
Moin,

in FGI hatten wir die sog. "Kleene-Konstruktion". Mein Problem ist, dass das Skript die nicht wirklich gut erklärt (zumindest nicht das, was ich wissen will), und dass der Begriff Kleene-Konstruktion anscheinend eine Erfindung der Uni Hamburg ist, auf jeden fall kennt weder Wikipedia noch Google noch das Vossel/Witt-Buch ein solches Verfahren. Ich bin auch nochmal die verschiedenen, in Wikipedia verlinkten verfahren, die Kleene erfunden haben soll, durchgegangen, und habe nichts in der Art gefunden.

Es kann natürlich auch sein, dass ich das Skript falsch verstanden habe, und das Verfahren gar nicht Kleene's Konstruktion heißt, sondern die abteilung des Skriptes einfach nur zeigt, wie Kleene drauf gekommen ist, aber ich hab auch sonst im Skript keinen Namen dafür gefunden…

Kennt jemand den "echten" namen dieses Verfahrens, damit ich es nachlesen kann?

Danke im Vorraus.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 16:18
Anonymer User
Ich kann die Folien nicht anschauen, Acrobat stürzt da regelmäßig ab, aber ich denke mal, es geht um http://de.wikipedia.org/wiki/Kleenesche_H%C3%BClle .

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 16:21
Anonymer User
Ach ja, genau, vielleicht sollte ich noch sagen, was die Kleene-Konstruktion ist:
Es ist ein verfahren, um aus einem Automaten eine Regular Expression zu erstellen.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 16:35
Anonymer User
Ich glaube, das Verfahren hat keinen gängigen Namen, und "Kleene's Konstruktion" ist der Versuch, einen solchen zu etablieren. Ganz gut beschrieben wird es mMn hier: http://www.inf.fh-flensburg.de/lang/theor/automat-zu-regulaerer-ausdruck.htm

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 16:54
Anonymer User
Danke, das ist schonmal eine gute Erklärung, wie man es machen kann.
Leider ist es nicht das Verfahren aus der Vorlesung (welches an das ganze 100% mathematisch herangeht, also erst einmal für jeden möglichen Übergang eine Expression erstellt, dann für jeden Übergang mit einem zwischenzustand die kombiniert, dann für jeden mit 2 zwischenzuständen, usw, bis man bei einer RegEx angekommen ist).

Ich hab mal die entsprechenden Seiten aus dem Skript fotographiert und angehängt. Qualität ist aber bescheiden…
Anhänge Foto 1.JPG , Foto 2.JPG

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 18:02
theorinix
Ich glaube, das Verfahren hat keinen gängigen Namen, und "Kleene's Konstruktion" ist der Versuch, einen solchen zu etablieren. Ganz gut beschrieben wird es mMn hier: http://www.inf.fh-flensburg.de/lang/theor/automat-zu-regulaerer-ausdruck.htm

Es war tatsächlich S.C. Kleene, der das Konzept der regulären Ausdrücke erfand und die Äquivalenz mit den von endlichen Atomaten akzeptierten Sprachen zeigte: S.C.Kleene, "Representation of Events in Nerve Nets and Finite Automata", in: C.E.Shannon & J.McCarthy, Automata Studies, Princeton Univ. Press. (1956) S. 3-24.
Nachzulesen u.A. in Hoproft/Motwani/Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexität.
Bücher sind sicher besser als wikipedia!!!

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 18:16
Anonymer User
Nachzulesen u.A. in Hoproft/Motwani/Ullman:

Kapitel 3.2 - um genau zu sein.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 18:16
Anonymer User
Ob Kleene das Verfahren entwickelt hat oder nicht war da auch nie die frage, so wie ich das sehe…

Es geht eher darum, wie das verfahren irgendwo heißt, wo ich es noch zusätzlich nachlesen kann.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 18:52
Anonymer User
Es geht eher darum, wie das verfahren irgendwo heißt, wo ich es noch zusätzlich nachlesen kann.
z.B. im Kapitel 3.2 im Hopcroft/Ullman/Motwani

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 19:26
Anonymer User
Hab leider momentan nur den Vossen/Witt und den Hoffmann…

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 21:01
Anonymer User
Dieses Verfahren ist ja jetzt nun nicht soo aufwenidg… vllt. kannst du ja erklären, wo dein Problem liegt und jemand hier kann dir evtl. helfen. Eigentlich musst du nur verstehen, was diese R^k_i,j bedeuten sollen und das steht auf Folie 25 in natürlicher Sprache. Das nächste was du verstehen musst ist die Rekursionsformel auf Seite 26. Wenn du das hast ist der Rest relativ stupides Einsetzen und etwas umformen (was teilweise vllt. nicht einfach ist, aber nichts mit dem Grundverständnis des Verfahrens zu tun hat).
Also wo genau ist dein Problem?

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 21:27
Anonymer User
Also, wir hatten das ganze in der Übung mit einem NFA mit zwei zuständen gemacht.
Dort haben wir die jeweiligen regulären Ausdrücke für R^0_1,1, R^0_1,2, R^0_2,2 und R^0_2,1 erstellt, und dann für R^1_1,2 und R^1_2,2 eingesetzt und "ausgerechnet", um das ergebnis dann in R^2_1,2 einzusetzen und damit die fertige Expression zu haben.

In der Übungsaufgabe habe wir hetzt einen Automaten mit 3 Zuständen. Am Anfang muss ich also wieder R^0_1,1 usw. aufstellen.
1. Frage: Muss ich alle kombinationen von R^0_x,y aufstellen, auch wenn es keine Verbindung von x zu y gibt? Also z.B. wenn es keine Verbindung von q1 zu q3 gibt, muss ich dann R^0_1,3 aufstellen (Und wie währe es dann geschrieben? Leere Menge?)?

Wenn ich mit dem Aufstellen dieser dinger fertig bin, kommen ja die R^1_x,y dran, so wie ich das verstehe, was dann wieder aus den Kombinationen der R^0's entsteht.
2. Frage: Das R^n_x,y bedeutet ja, so wie ich das verstanden habe, eine Eingabe, die von qx zu qy über n zustände führt (Also im Falle von 1 entweder einen Loop auf einem der Zustände dreht (z.B. q1->q1->q2) oder einen weiteren Zwischenzustand qz passiert (q1->q2->q3)). Habe ich das so richtig verstanden? Das enthält somit auch die Frage: Gibt es bei R^1 eine Verbindung von q1 zu q3, wenn wir q1->q2->q3 im Automaten haben?

In der Präsenzaufgabe mussten wir das ganze bis R^2 machen.
3. Frage: Das mag zwar im Zweifel offensichtlich sein, aber sicherheitshalber: Bei einem Automaten mit k Zuständen gehen wir immer bis R^k, richtig? So lese ich die Definition zumindest. Im falle unseres 3-Zustands-Automaten ist das finale Ziel dann also R^3_1,3, wenn man 1 also Start und 3 als Endzustand annimmt?

Und, wenn ich noch um diesen kleinen Tipp bitten dürfte: Die Zusammensetzung von R^3_1,3 währe dann? Meine momentane Idee währe:
R^3_1,3 = R^2_1,1 U R^2_1,2 x (R^2_2,2)* x R^2_2,3 x (R^2_3,3)*
U = Vereinigung, x = Konkatination

Danke für die Hilfe.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 22:02
Anonymer User
Ich bin mir nicht sicher, ob ich deine Fragen alle richtig verstanden habe, deshalb schreibe ich etwas allgemeines und falls dabei eine der Fragen unbeantwortet bleibt, musst du nochmal Bescheid sagen.

Also erstmal das Verfahren ist definiert für einen DFA. Das sollte aber ja kein Problem darstellen, weil man die ja umwandeln kann. Der Automat in der Übung war netterweise auch schon deterministisch.

Was du zu den Rs geschrieben hast ist fast richtig. Es bedeutet aber nicht, dass du n Zwischenzustände hast, sondern, dass du als Zwischenzustände die Zustände von 1 bis n benutzen darfst (also nicht musst… außerdem ist nicht die Anzahl der zwischenzustände entscheidend).

Jetzt lese ich raus, dass du nicht genau weißt, wie lange du das machen musst.
Das Ergebnis, was du bekommen willst ist ja eigentlich der Ausdruck, der die Sprache beschreibt, die auf allen Wegen von einem Startzustand zu einem Endzustand über beliebige Zwischenzustände möglich ist.
Wenn du nur einen Endzustand hast (angenommen der heißt z5) und einen Startzustand (angenommen der heißt z1) und 7 Zustände, wäre das R^7_1,5… also der Weg von z1 nach z5 über alle 7 Zustände. Wenn du jetzt mehr als einen Endzustand hast, musst du das R für jeden Endzustand berechnen und am Ende vereinigen. Das steht so unten auf Folie 25 (L(A) = Vereinigung über alle Endzustände q_j von R^n_1,j)

Wenn du damit anfängst und die Rekursionsformel anwendest, siehst du ja, welche Rs du berechnen musst. Du musst dir dann halt deine Zwischenergebnisse merken, damit du nicht Sachen doppelt berechnest. Wenn du es bottom up machst, musst du im Blick haben, wo du hin willst.

Ich hoffe das hilft erstmal weiter.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 22:05
Anonymer User
Ich sehe gerade im Skript "Konstruktion funktioniert auch für NFA". Bei mehreren Startzuständen muss man das Verfahren dann vermutlich etwas variieren, aber das ist bei der Übungsaufgabe nicht der Fall.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-15 22:15
Anonymer User
Okay, danke für die Erklärung, damit kann ich zumindest schonmal anfangen zu arbeiten. So wie ich mich kenne, werde ich zwar wieder irgendwo hängen bleiben, aber dann kann ich ja einfach noch eine weitere frage stellen.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-16 16:46
Anonymer User
Ich hab nochmal eine kurze frage, die mit der Vereinigungsfunktion zu tun hat:
Angenommen, ich habe 2 mengen: {a,b} und {(a,b)+} (Oder wie auch immer man die darstellung von regular-expression-Mengen richtig macht). Wenn ich die beiden vereinige, erhalte ich dann {(a,b),(a,b)+}? Oder {(a,b)+}? Oder was ganz anderes? Oder hab ich irgendwo vorher nen fehler und diese Konstellation ist gar nicht möglich? ;-)

Danke im Vorraus.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-16 17:32
doodles
Ich weiß leider nicht genau, welche Mengen du meinst… Was du da stehen hast, scheint mir eine Mischung aus Regulärem Ausdruck und Menge zu sein und ist daher unverständlich. Guck dir nochmal genau die Definition von regulären Ausdrücken an… so schwer ist das nicht.

Grundsätzlich machst du den Schritt von den Mengen zu den regulären Ausdrücken aber erst ganz zum Schluss. Das heißt, wenn du noch Sachen vereinigen möchtest um eine kompaktere Form zu bekommen, solltest du noch mit den Mengen arbeiten.

Falls du die Mengen
{8,9} und {8,9}+ (wobei das + hochgestellt ist) meinst, dann wäre die Vereinigung wieder {8,9}+.

Überleg dir welche Wörter in der jeweiligen Menge enthalten sind, wenn du nicht weißt, was die Vereinigung ergibt.
Die Menge {8,9} enthält die Wörter 8 und 9
Die Menge {8,9}+ enthält die Wörter 8, 9, 88, 89, 98, 99, 888, …

8 und 9 sind also schon in der zweiten drin.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-16 19:00
Anonymer User
Jop, ich meinte es genau auf die Art, die du meintest. Und auf die Art hab ich gar nicht drüber nachgedacht… Klar, irgendwie macht das ne menge sinn ;-)

Danke fürs augen öffnen.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-16 19:11
Anonymer User
Nochmal eine Frage zur Rekursionsformel:
Zur erinnerung: Die formel war:
R^k_i,j = R^k-1_i,j U R^k-1_i,k x (R^k-1_k,k)* x R^k-1_k,j (Bei k >= 1)
Wieder mit x = konkertination und U = vereinigung

Bei dem Teil nach dem Vereinigungssymbol:
Setze ich für k immer das aktuelle k ein, oder darf ich da einen beliebigen Zustand von q1 bis qk nehmen? Ich habe bisher immer das aktuelle k eingesetzt, und es sieht auch so aus, als wenn es passen würde, aber trotzdem gehe ich lieber noch einmal sicher, bevor ich die gesamte Aufgabe noch einmal durchrechnen darf…

Oh, und fängt die Zustandszählung bei q1 oder q0 an? Ist irgendwie auch wichtig. In der Präsenzaufgabe war es, glaube ich, q1 und q2, deswegen hab ich beim Automaten mit 3 Zuständen die Nummerierung q1 q2 und q3 benutzt, aber auch hier wieder, lieber sicherheitshalber nachfragen als am Ende alles neu machen müssen…

RE: FGI-1: "Kleene's Konstruktion" 2011-04-16 21:28
Anonymer User
Ich habe es jetzt einmal so zu ende gerechnet, wie ich es hier beschrieben hatte, und bin auf das richtige endergebnis gekommen. Insofern scheint es zumindest in diesem fall zu funktionieren. Eine Bestätigung, dass es so richtig ist, währe trotzdem super… Just in case ;-)

RE: FGI-1: "Kleene's Konstruktion" 2011-04-17 11:17
doodles
Das k ist natürlich innerhalb einer Formel überall gleich… ist doch Mathematik.

Es ist sinnvoller bei q1 anzufangen, weil du mit R^0 den Fall hast, dass du keinen Zwischenzustand hast und wenn du bei q0 anfangen würdest, müsstest du für diesen Fall R^-1 nehmen und als Ziel R^n-1 und das ist dann etwas fummelig.

Das sind aber beides Sachen, auf die du auch selber hättest kommen können. Eigenständig denken ist aber nach wie vor erlaubt.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-17 18:25
Anonymer User
Einen wunderschönen guten Abend wünsche ich!

Ich sitze momentan gerade an der das Thema betreffenden Übungsaufgabe und beiße mir die Zähne aus… folgendes Problem:

Die Rekursionsformel ist ja wie oben auch schon angegeben:
R^k_i,j = R^k-1_i,j U R^k-1_i,k x (R^k-1_k,k)* x R^k-1_k,j (Bei k >= 1)

In der vorliegenden Aufgabe sind:
R^0_1,1 = {ɛ, a}
R^0_1,2 = {a}
R^0_2,2 = {ɛ, a, b}
R^0_2,3 = {a}
R^0_3,3 = {ɛ, b}

damit sollte nach Rekursionsformel
R^3_1,3 = R^2_1,3 + R^2_1,3 x (R^2_3,3)* x R^2_3,3 (+ ist Vereinigung, x Konk.)
sein, korrekt? (war oben anders angegeben).

Rekursiv würde R^2_1,3 = R^1,3 + R^1,2 x (R^1_2,2)* x R^1_2,3 sein, also die erste Komponente der "Endlösung".

Die letzte Komponente (fett markiert) von R^2_1,3 wäre ja
R^1_2,3 = R^0_2,3 + R^0_2,1 x (R^0_1,1)* x R^0_1,3={a}+{leer}x({ɛ, a})* x {leer}={leer}
aufgrund der Tatsache, dass die Konkatenation mit der leeren Menge immer die leere Menge ergibt, richtig?
mit R^1_2,3={leer} wäre aufgrund der Konk. auch R^2_1,3={leer} und R^3_1,3={leer}…

Nun, das scheint mir irgendwie zu einfach für eine Übungsaufgabe und genau da liegt mein Problem, ich sehe den Fehler nicht…

Bitte helft mir auf die Sprünge, wäre euch sehr dankbar!

RE: FGI-1: "Kleene's Konstruktion" 2011-04-17 20:52
doodles
Also das R^3_1,3={leer} unmöglich richtig sein kann, sollte doch sofort ersichtlich sein. Wenn du den Automaten anguckst siehst du doch direkt, dass er nicht die leere Menge akzeptiert.

Ich weiß jetzt nicht genau, ob du richtig eingesetzt hast, denn das werde ich hier nicht überprüfen. Buchstaben durch Zahlen zu ersetzen sollte wohl für jeden noch so mathe-unaffinen Menschen möglich sein.

Einen Denkfehler, den ich aber sehe ist das Nichtbeachten der Bindungsstärken.
Bei C={} gilt eben nicht A + B x C = {} sondern A + B x C = A, weil die Konkatenation stärker bindet als die Vereinigung.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-17 23:41
Anonymer User
…ding dong… danke!

RE: FGI-1: "Kleene's Konstruktion" 2011-04-18 13:53
theorinix
…ding dong… danke!

ja, und bzw. aber eine Bemerkung hätte ich noch an die meisten Teilnehmer dieses threads:

Mengen werden NIE konkateniert! Die Operation auf den Mengen von Wörtern, die die einzelnen Elemente, also die Wörter, konkateniert nennt man Komplexprodukt!
Die am häufigsten benötigten Operationen auf allen Mengen sind Durchschnitt, Vereinigung, carthesisches Produkt und Komplexprodukt. (DM lässt grüßen.)
Bitte nicht erst falsche Schreib- und Sprechweisen aneignen, sondern gleich richtig einüben;
und dann wirklich dingelingeldank.

RE: FGI-1: "Kleene's Konstruktion" 2011-04-19 10:03
Praktix
Mengen werden NIE konkateniert! Die Operation auf den Mengen von Wörtern, die die einzelnen Elemente, also die Wörter, konkateniert nennt man Komplexprodukt!

Hallo,

dies würde ich nicht so eng sehen. Ja, in den Folienkopien und auch im F2 Skript wird diese feine Unterscheidung gemacht. Allerdings sprechen sowohl der H/U als auch der V/W von der Konkatenation von Sprachen.

H/U Seite 86 (siehe auch http://books.google.com/books?ei=STitTbLSJMzg4wa95oiVCw&ct=result&id=7YEZAQAAIAAJ&dq=hopcroft+ullman&q=concatenation#search_anchor)

V/W: Seite 17 (siehe auch http://books.google.com/books?id=Zo7I8kutRVIC&lpg=PP1&dq=vossen%20witt&pg=PA17#v=onepage&q&f=false)

Auch der Informatik Duden und die Wikipedia sehen das so. Allerdings kann es sein, dass die englische Sprache hier auf die Bezeichnungen Einfluss nimmt.

Grüße