Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

3 Pluspunkte 0 Minuspunkte
213 Aufrufe
Hallo,

gibt es eine Art Kochrezept zum erstellen von Regulären Ausdrücken aus endlichen Automaten?

Einige Parallelen denke ich sind offensichtlich, wie dass z.b. eine Schleife später wie ein * behandelt wird, aber bei komplexen Aufgaben wie in diesem Fall, ist es gar nicht so einfach alle Fälle abzudecken. Oft vergisst man beispielsweise die trivialen Wörter und bei vielen Klammern fehlt mir meist auch ein bisschen der Überblick.

Da jede reguläre Sprache ja aber durch einen endlichen Automaten und einen regulären Ausdruck dargestellt werden kann, müssen hier doch bestimmt Parallelen liegen, sodass durch ein einfaches Vorgehen die Automaten in reguläre Ausdrücke transformiert werden können, oder nicht?

Meines Wissens haben wir kein Verfahren dieser Art kennen gelernt. Falls doch würde ich mich freuen, wenn mir jemand sagen könnte wo ich dieses im Skript oder in den Übungsaufgaben fnden kann.

Vielen Dank!
in REC-AI von updrr updrr Eins-Komma-Null-Anwärter(in) (4.7k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Leider ist das mit regulären Ausdrücken nicht ganz so einfach. Ja, sie sind auf endliche Automaten abbildbar und umgekehrt, aber der Algorithmus EA => RA ist nicht ganz einfach und führt vor allem oft zu sehr großen regulären Ausdrücken. Sie können das ja im XWizard testen, indem Sie bei einem endlichen Automaten auf die Konversionsmethode "Regulärer Ausdruck" klicken. Der Algorithmus, der dort implementiert ist, kann im "Hopcroft/Ullman" nachgelesen werden, siehe Info-II-Literaturliste, aber er geht deutlich über die Vorlesung hinaus.

Kurz gesagt, wir werden Ihnen in der Klausur sicher nur einfache endliche Automaten (bzw. reguläre Ausdrücke) zum Umwandeln vorsetzen - und Sie brauchen dann halt ein "gutes Auge", das heißt eben etwas Übung, um solche Aufgaben zu lösen.

Ein paar "Kochrezepte" für Spezialfälle gibt es natürlich schon, etwa, dass es sinnvoll ist, sich von Endzuständen aus entlangzuhangeln.

Viele Grüße

Lukas König
von Dozent (10.1m Punkte)  
Eindeutigkeit Lösung reguläre Ausdrücke
...