Umwandlung DFA in regulären Ausdruck?

Andreas_Brand · 10. November 2019 um 00:06

Hallo,

ich beschäftige mich gerade ein bisschen mit Automatentheorie und
formalen Sprachen. Dabei habe ich zu Übungszwecken einen
deterministischen finiten Automaten (=DFA) zum Erkennen von
geradzahlig vielen Nullen und Einsen entwickelt, siehe

http://www.bitschmied.de/abbildungen/dfa-fuer_geradz…

Wie man sieht, hat der Automat 9 Zustände. Aber wie leite ich nun aus
diesem Automat den zugehörigen regulären Ausdruck ab?

Wenn ich die 6 kürzesten Pfade (unter Berücksichtigung der Schleifen
per *) in diesem Automatengraphen mit der Länge 4 per ODER verknüpfe
komme ich nur auf eine Teilmenge der Möglichkeiten:

Pfad | regulärer Ausdruck 
------------------------------------------------------ 
[P1] 1-2, 2-3, 3-6, 6-9 | 11(11)\*00(00)\*
[P2] 1-2, 2-5, 5-6, 6-9 | 101(11)\*0(00)\*
[P3] 1-2, 2-5, 5-8, 8-9 | 100(00)\*1(11)\*
[P4] 1-4, 4-7, 7-8, 8-9 | 00(00)\*11(11)\*
[P5] 1-4, 4-5, 5-8, 8-9 | 010(00)\*1(11)\*
[P6] 1-4, 4-5, 5-6, 6-9 | 011(11)\*0(00)\*

Z.B. beschreibe ich mit den obigen Ausdrücken nicht die gültige
Eingabe „101101“.

Wie müsste der vollständige reguläre Ausdruck lauten
und wie kann man ihn systematisch aus dem DFA herleiten?

Hat jemand Literatur- oder Linkempfehlungen zum Thema?

Gruß,
-Andreas.

Marvin_c530f3 · 10. November 2019 um 00:06

Hallo Andreas,

ich beschäftige mich gerade ein bisschen mit Automatentheorie
und
formalen Sprachen
Hat jemand Literatur- oder Linkempfehlungen zum Thema?

vielleicht etwas knapp:
http://www.mathematik.uni-marburg.de/~gumm/Skripten/…
etwas allgemeiner, aber auch zu regulären Ausdrücken DFA
http://www.grundstudium.info/theorie/node1.php
und aller guten Dinge sind drei
http://www.cvgpr.uni-mannheim.de/Lehre/Pi1/Skript/Au…

Viel Erfolg
Klaus Bernstein

Andreas_Brand · 10. November 2019 um 00:08

Hallo Klaus.

die Links gehen schon in die richtige Richtung.

Allerdings komm ich bei meinem konkreten DFA
noch nicht auf den korrekten Regex.

Das Beispiel zur schrittweisen Reduktion des Graphen
ist zu einfach gestrickt und nicht auf meinen stark
„vermaschten“ DFA direkt anwendbar (siehe Zustand 5!)
und die erwähnte vollständige „rekursive Lösung“ ist
mir ohne ein gutes Beispiel noch zu abstrakt.

Vielleicht kann mir noch jemand in seinen eigenen
Worten erklären, wie er aus meinen DFA unter
http://www.bitschmied.de/abbildungen/dfa-fuer_geradz…
den Regex herleiten würde?

Gruß,
-Andreas.

Peter_TOO · 10. November 2019 um 00:08

Hallo Andreas,

Vielleicht kann mir noch jemand in seinen eigenen
Worten erklären, wie er aus meinen DFA unter
http://www.bitschmied.de/abbildungen/dfa-fuer_geradz…

Irgendwie verstehe ich nicht wieso du 9 Zustände benötigst ?
Für eine Luxus-Ausführung mit 3 Endzuständen komme ich auf 6 Zustände, andernfalls reichen mir 4 aus.

Es gibt 3 Ereignisse:

‚0‘
‚1‘
ENDE

Zustände:

START, warten bis es losgeht
UNGERADE Anzahl an ‚1‘
GERADE Anzahl an ‚1‘
FEHLER, z.B. ENDE im Zustand START erhalten. Dabei gibt es ja keine gültige Aussage über die Anzahl ‚1‘
ENDE_GERADE
ENDE_UNGERADE

Zustand 4., 5. und 6. können im Prinzip auch zu einem zusammengefasst werden.

MfG peter(TOO)

Moritz_fe1b4f · 10. November 2019 um 00:08

Hallo,

ich beschäftige mich gerade ein bisschen mit Automatentheorie
und
formalen Sprachen. Dabei habe ich zu Übungszwecken einen
deterministischen finiten Automaten (=DFA) zum Erkennen von
geradzahlig vielen Nullen und Einsen entwickelt, siehe

http://www.bitschmied.de/abbildungen/dfa-fuer_geradz…

0 ist auch eine gerade Zahl, d.h. dein Automat sollte den leeren String akzeptieren.

Folgendes sollte eigentlich gehen:

A B
| 0 |
| |
|1 1|
| 0 |
C D

wobei A sowohl Anfangs- als auch Endzustand ist.

Grüße,
Moritz

Peter_TOO · 10. November 2019 um 00:08

Hallo,

0 ist auch eine gerade Zahl, d.h. dein Automat sollte den
leeren String akzeptieren.

Ohne speziellen Endzustand gehts sogar mit 2 Zuänden:

 1 
 ---------\> 
Gerade Ungerade

Der Anfangszustand ist "Gerade"; eine '0' verändert nichts am Zustand.

MfG Peter(TOO)

Moritz_fe1b4f · 10. November 2019 um 00:08

Hallo,

0 ist auch eine gerade Zahl, d.h. dein Automat sollte den
leeren String akzeptieren.

Ohne speziellen Endzustand gehts sogar mit 2 Zuänden:

1
--------->
Gerade Ungerade

Der Anfangszustand ist „Gerade“; eine ‚0‘ verändert nichts am
Zustand.

Ich glaube, dass wir uns gerade missverstanden haben.

Wenn ich den OP richtig verstanden habe, will er einen Automaten (und eine regex), die alle Strings akzeptiert, die aus einer geraden Anzahl von '0’en und einer geraden Anzahl von '1’en bestehen.

Das macht dein Automat wohl kaum.

Worauf ich hinweisen wollte, ist die Tatsache, dass diese Definition auch den String der Länge 0 einschliesst, also den leeren String.

Grüße,
Moritz

Andreas_Brand · 10. November 2019 um 00:09

Hallo Moritz.

Wenn ich den OP richtig verstanden habe, will er einen
Automaten (und eine regex), die alle Strings akzeptiert, die
aus einer geraden Anzahl von '0’en und einer geraden Anzahl
von '1’en bestehen.

Korrekt.

Worauf ich hinweisen wollte, ist die Tatsache, dass diese
Definition auch den String der Länge 0 einschliesst, also den
leeren String.

An der Stelle gilt das Verhalten meines Automaten:

Leerstring ist nicht erlaubt
das Wort muss mindestens zwei Nullen und zwei Einsen erhalten

Wie komme ich jetzt auf den Regex?

Gruß,
-Andreas.

Moritz_fe1b4f · 10. November 2019 um 00:09

Hallo,

Worauf ich hinweisen wollte, ist die Tatsache, dass diese
Definition auch den String der Länge 0 einschliesst, also den
leeren String.

An der Stelle gilt das Verhalten meines Automaten:

Leerstring ist nicht erlaubt

das Wort muss mindestens zwei Nullen und zwei Einsen
erhalten

Gut zu wissen

Wie komme ich jetzt auf den Regex?

Gute Frage.
Ich bin in der theoretischen Informatik nicht so bewandert… gibt es einen Satz, der garantiert, dass es zu jedem DFA eine entsprechende Regex gibt?

Je mehr ich darüber nachdenke, desto unwahrscheinlicher finde ich es, dass diese Regex tatsächlich existiert.
Mit den Perl 6 rules könnte ich so etwas ausdrücken, aber die sind alles andere als regulär

Grüße,
Moritz

McGee_55a7a1 · 10. November 2019 um 00:09

An der Stelle gilt das Verhalten meines Automaten:

Leerstring ist nicht erlaubt

das Wort muss mindestens zwei Nullen und zwei Einsen
erhalten

Wie komme ich jetzt auf den Regex?

Hallo Andreas,

nehmen wir als Grundlage den Link

http://www.grundstudium.info/theorie/node54.php

der von Klaus gepostet wurde.

Wörter sind Wege im Graphen.
Zunächst schauen wir uns Wege ohne Zwischenzustände (k=0) an.
Dafür benötigen wir eine 9 x 9 Tabelle,
wo drin steht, welcher Buchstabe erzeugt wird, wenn wir von Zustand i nach j gehen

1 2 3 4 5 6 7 8 9
1 . 1 . 1 . . . . .
2 . . 1 . 0 . . . .
3 usw.
4
5
6
7
8
9

Die Einträge sind mit a_{i,j}^0 bezeichnet, also z.B.:
a_{2,5}^0=0
a_{1,3}^0=leeres Wort

Danach gehen wir zu k>0, also zu Wegen, die als Zwischen-Zustände 1,…,k enthalten dürfen:
Alle diese Wege lassen sich zerlegen in Wege, die Zustand k nicht benutzen (erster Teil der Rekurison), und Wege, die direkt zum Zustand k gehen, dort Kreise durchlaufen und dann zum Zustand j laufen:

a_{i,j}^k = a_{i,j}^k-1 + a_{i,k-1}^k-1 (a_{1,1}^k-1)* a_{1,j}^k-1

Nehmen wir an, wir haben bereits ausgerechnet:
a_{1,5}^1=leeres Wort
a_{1,2}^1=1
a_{2,2}^1=leeres Wort
a_{2,5}^1=0

dann ist a{1,5}^2= a_{1,5}^1 + a_{1,2}^1 ( a_{2,2}^1 )* a_{2,5}^1
= 1 0

Obige Formel läßt sich hinschreiben, indem auf bereits ausgerechnete Werte zugegriffen wird.

Das Sternchen kommt zum tragen z.B. bei

a_{2,3}^3 = a_{2,3}^2 + a_{2,3}^2 ( a_{3,3}^2 )* a_{3,3}
= 1 + 1 (11)* 11

wenn ich mich nicht vertan hab

Nachdem Du dann alle 729 a_{i,j]^k hingeschrieben hast ,
ist a_{1,9}^9 der gesuchte reguläre Ausdruck für deinen Automaten,
da 1 Startzustand und nur 9 ein akzeptierender Zustand ist.
Ansonsten müßte man hier vereinigen über alle Wege zu aktz. Zuständen.

Bitte dein Ergebnis posten (falls Du es programmierst),
da mich interessiert, wie ein RegAusdruck für diese Sprache aussieht.

Grüße
Thorsten

Andreas_Brand · 10. November 2019 um 00:09

Hallo Moritz.

Wie komme ich jetzt auf den Regex?

Gute Frage.
Ich bin in der theoretischen Informatik nicht so bewandert…
gibt es einen Satz, der garantiert, dass es zu jedem DFA eine
entsprechende Regex gibt?

Ja, das ist gerade das spannende:

DFA, NFA, Regex und reguläre Grammatik sind
äquivalente Möglichkeiten zur Beschreibung regulärer Sprachen.

Sie können dabei alle ineinander umgewandelt werden. Soweit
zur Theorie. Ich wollte das nun mal in Praxis machen. Aber
wie so oft, gibt es halt ein paar „Anlaufschwierigkeiten“ …

Meistens hat man in Praxis aber einen Regex gegeben und sucht dazu
den passenden DFA: Die Beschreibung der Tokens einer Sprache
findet also als regulärer Ausdruck statt und diese werden
dann von einem Lexer (lex, flex, …) automatisch in einen
DFA umgewandelt.

Je mehr ich darüber nachdenke, desto unwahrscheinlicher finde
ich es, dass diese Regex tatsächlich existiert.
Mit den Perl 6 rules könnte ich so etwas ausdrücken, aber die
sind alles andere als regulär

Wie lautet denn Deine „irregulärer“ Ausdruck in Perl?

Gruß,
-Andreas.

McGee_55a7a1 · 10. November 2019 um 00:10

Hallo Andreas,

Hat jemand Literatur- oder Linkempfehlungen zum Thema?

habe gerade unter http://www.jflap.org/ ein Applet gefunden,
welches DFAs in reguläre Ausdrücke umwandelt,
auch mit Anzeige der Zwischenschritte.

Hier ein reguläre Ausdruck, den das Programm ausgegeben hat:

(1(11)*100+0(00)*011+(1(11)*0
+0(00)*1+1(11)*101+0(00)*010)(11+00)*
(10+01))(00+11+(01+10)(11+00)*(10+01))*

Grüße
Thorsten

Andreas_Brand · 10. November 2019 um 00:10

Hallo Thorsten.

habe gerade unter http://www.jflap.org/ ein Applet gefunden,
welches DFAs in reguläre Ausdrücke umwandelt,
auch mit Anzeige der Zwischenschritte.

Hier ein reguläre Ausdruck, den das Programm ausgegeben hat:

(1(11)*100+0(00)*011+(1(11)*0
+0(00)*1+1(11)*101+0(00)*010)(11+00)*
(10+01))(00+11+(01+10)(11+00)*(10+01))*

Klasse, der Ausdruck funktioniert, wie meine Tests im RegexCoach
(http://weitz.de/regex-coach/) ergeben!

Vielen Dank für den Link auf das JFLAP-Tool, dass macht die Automatentheorie gleich viel anschaulicher.

Bei Gelegenheit werde ich mal Deinen Algorithmus zur Umwandlung DFA->Regex implementieren.

Gruß,
-Andreas.