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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

3 Pluspunkte 0 Minuspunkte
243 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
...