Konvertieren eines NFA in Regex mithilfe des GNFA-Algorithmus?

Also habe ich lange versucht, dies zu knacken und habe fast das Gefühl, dass ich mich über diese Frage in Schleifen befinde.

Angesichts der folgenden NFA:

Geben Sie hier die Bildbeschreibung ein

Verwenden Sie den GNFA-Algorithmus, um den regulären Ausdruck zu erhalten.

Ich verstehe, dass Sie für den ersten Schritt (Hinzufügen leerer Zustände) Folgendes haben würden: Geben Sie hier die Bildbeschreibung ein

Der nächste Schritt wäre das Entfernen des Status [q1], den ich erhalten würde: Geben Sie hier die Bildbeschreibung ein

Schließlich würde das Entfernen von [q2] Folgendes ergeben: Geben Sie hier die Bildbeschreibung ein

Die Antworten, die andere haben, sind jedoch: $(a \cup bb^*a)^*bb^*$ Was keinen Sinn ergibt, wie ich bekam, $a^*b(b \cup aa^*b)^*$ ? Ein GNFA (verallgemeinerter nichtdeterministischer endlicher Automat) wird wie folgt beschrieben:

Ein GNFA ähnelt einem NFA, muss jedoch bestimmte Regeln einhalten:

Es hat nur einen Akzeptanzzustand
In den Ausgangszustand treten keine Übergänge ein
Der Akzeptanzzustand hat keine Übergänge
Ein Übergang kann einen beliebigen regulären Ausdruck und nicht nur ein Symbol aus dem Alphabet bezeichnen. Beachten Sie, dass ein Symbol eine Art regulärer Ausdruck ist.

Darüber hinaus können wir eine NFA wie folgt in eine GNFA umwandeln:

Fügen Sie einen neuen Startzustand mit einem ε-Übergang zum alten Startzustand hinzu
Fügen Sie einen neuen Akzeptanzzustand mit ε-Übergängen von den alten Akzeptanzzuständen hinzu
Wenn Pfeile mehrere Beschriftungen haben oder wenn zwischen zwei Zuständen mehrere Pfeile liegen, ersetzen Sie sie durch die Vereinigung (oder) dieser Beschriftungen

automata finite-automata regular-expressions nondeterminism Anish B.
quelle

@ Jeff, Es wird ein verallgemeinerter nichtdeterministischer endlicher Automat (GNFA) genannt

Anish B

Hinweis: Welche Sprache akzeptiert Ihr EDA tatsächlich? Sie sollten in der Lage sein, eine englische Beschreibung der akzeptierten Sprache herauszufinden, indem Sie sich das DFA ansehen. Nun, welcher der beiden regulären Ausdrücke

(a + b b^{*} a) b b^{*}

$(a+bb^*a)bb^*$ und

a^{*} b (b + a a^{*} b)^{*}

$a^*b(b+aa^*b)^*$ diese Sprache richtig beschreiben?

JeffE

@JeffE Ich stimme auch zu, dass einer sinnvoller ist als der andere. Wenn Sie jedoch den GNFA-Algorithmus verwenden, ist dies normalerweise nicht dasselbe wie das Lesen in einer englischen Beschreibung, daher meine Verwirrung.

Anish B

Ich habe nie gesagt "eins macht mehr Sinn als das andere". Ich schlage vor, dass Sie das Problem anhand der ersten Prinzipien lösen, indem Sie Ihr Gehirn anstelle des GNFA-Algorithmus verwenden und dann überprüfen, welcher der beiden regulären Ausdrücke korrekt ist. (Anmerkung: Ich habe nicht schreiben „ welche der beiden regulären Ausdrücken ist richtig.“)

JEFFE

Siehe auch unsere Referenz Frage für weitere Techniken, von denen alle unterschiedliche Ausbeute (aber immer noch korrekt) Ergebnisse.

Raphael

Sie möchten wissen, warum "die anderen" einen anderen Ausdruck erhalten haben?

Wenn ein regulärer Ausdruck konstruiert wird, gibt es keine eindeutige richtige Antwort. Es gibt normalerweise mehrere Ausdrücke, "die Sinn machen". In diesem Fall verwenden Sie die Zustandseliminierungsmethode (ich habe dies unter dem Namen Brzozowski und McCluskey gelernt). Hier bestimmt die Reihenfolge der Entfernung den gefundenen Ausdruck. Also: Was bekommen Sie beim Entfernen? $q2$ zuerst?

Sie können auch "clevere Tricks" während des Baus machen. In Ihrem Beispiel haben Sie $b\cup aa^*b$ das ist äquivalent zu $a^*b$ .

Hendrik Jan.
quelle

+1 für b U aa*b = a*bund den Namen Brzozowski und McCluskey

Maha

Konvertieren eines NFA in Regex mithilfe des GNFA-Algorithmus?

Antworten: