Wie konvertiere ich eine NFA mit überlappenden Zyklen in einen regulären Ausdruck?

11

Wenn ich das richtig verstehe, hat NFA die gleiche Ausdruckskraft wie reguläre Ausdrücke. Oft ist es einfach, äquivalente reguläre Ausdrücke aus NFA abzulesen: Sie übersetzen Zyklen in Sterne, Kreuzungen als Alternativen und so weiter. Aber was ist in diesem Fall zu tun:

Geben Sie hier die Bildbeschreibung ein
[ Quelle ]

Die überlappenden Zyklen machen es schwierig zu sehen, was dieser Automat akzeptiert (in Bezug auf reguläre Ausdrücke). Gibt es einen Trick?

zell
quelle
2
Es wäre gut, wenn Sie im Diagramm den Anfangs- und Endzustand angeben könnten: einen kleinen Pfeil zum Anfangszustand und einen Doppelkreis als Endzustand. Außerdem ist es schwierig zu wissen, wo Sie falsch liegen, wenn Sie keinen Hinweis darauf geben, was Sie versucht haben.
Dave Clarke
Vielleicht kann Ihnen dieses Dokument helfen: Es erklärt deutlich, wie eine NFA in eine RE konvertiert wird.
Vor dem
1
Warum ist es schwer? Haben Sie einen der kanonischen Algorithmen ausprobiert? Was ist der beste Ansatz, den Sie tun können?
Raphael
3
Ich habe bearbeitet, um die Frage (imho) interessant und gut für diese Seite zu machen. Sehen Sie sich den Revisionsverlauf an, um sich eine Meinung zu bilden.
Raphael
1
Ich habe eine Antwort parat, die Ihre NFA in einen regulären Ausdruck umwandelt, aber ich habe sie gelöscht: Raphaels Antwort gibt Ihnen die Methode, die Sie benötigen, um es selbst zu tun (es gibt auch einen Link zu einem Beispiel), sodass Sie etwas Übung bekommen können, wenn Sie wollen. Wenn Sie immer noch meine Lösung wollen, werde ich meine Antwort wiederherstellen.
Alex Ten Brink

Antworten:

5

Anstatt "abzulesen", sollten Sie eine von mehreren kanonischen Methoden anwenden, um dies zu tun. Das mit Abstand schönste, das ich gesehen habe, ist eines, das den Automaten als Gleichungssystem von (regulären) Sprachen ausdrückt, das gelöst werden kann. Es ist besonders schön, da es prägnantere Ausdrücke zu liefern scheint als andere Methoden.

Ich habe dieses Dokument geschrieben , in dem die Methode für Studenten im letzten Sommer erklärt wurde. Es bezieht sich direkt auf eine bestimmte Vorlesung; Die erwähnte Referenz ist eine typische Definition von regulären Ausdrücken. Ein Beweis von Ardens Lemma (ein notwendiges Ergebnis) ist enthalten; eine für die Richtigkeit der Methode fehlt. Wie ich in der Vorlesung erfahren habe, habe ich leider keine Referenz.

Kurz gesagt: Erstellen Sie für jeden Zustand die Gleichungqich

Q.ich=qicheinqjeinQ.j{{ε}}, qichF., sonst

wobei die Menge der Endzustände ist und q i a q j bedeutet, dass es einen Übergang von q i zu q j gibt, der mit a gekennzeichnet ist . Wenn Sie als + oder lesen (abhängig von Ihrer Definition des regulären Ausdrucks), sehen Sie, dass dies eine Gleichung für reguläre Ausdrücke ist.Fqiaqjqiqja+

Das Lösen (unter Verwendung von Ardens Lemma ) ergibt einen regulären Ausdruck für jeden Zustand, der genau die Wörter beschreibt, die ab q i akzeptiert werden können ; daher ist Q 0 (wenn q 0 der Anfangszustand ist) der gewünschte Ausdruck.QiqiQ0q0

Die Anwendung auf den gegebenen Automaten bleibt als Übung; Ein vollständiges Beispiel finden Sie im oben verlinkten Dokument .

Siehe auch hier, wo ich eine ähnliche Antwort gepostet habe.

Raphael
quelle
1
In dieser Referenzfrage finden Sie weitere allgemeine Methoden.
Raphael
3

Wenn es nur eine Kette von Staaten ohne Schleife gäbe, würden Sie wissen, was zu tun ist?

Wenn es eine einfache Schleife ohne diese überlappende Verzweigung gäbe, würden Sie wissen, was zu tun ist?

(Wenn die Antwort "Nein" lautet, denken Sie zuerst an diese Fälle.)

Die Idee ist nun, den Automaten schrittweise zu transformieren, um ihn in eine Form zu bringen, in der Sie diese Muster erkennen können: Ketten, Schleifen und divergierende Pfade, die am Ende wieder zusammenlaufen (was zu einem Wechsel führt). Achten Sie bei jedem Schritt der Transformation darauf, dass der transformierte Automat immer noch dieselbe Sprache erkennt.

Beachten Sie, dass dies ein nicht deterministischer Automat ist. Das, was Sie gepostet haben, ist zwar deterministisch, muss aber bei der Transformation nicht so bleiben.

q2q1fq2gq3q4q2q5q4jq5gq3

q3,q4,q5q3q3(hjg)

Achten Sie darauf, zu überprüfen, welche Zustände endgültig sind. Es kann hilfreich sein, sich zuerst keine Sorgen zu machen und eine große Schleife zu erstellen und dann Teile zu duplizieren, die auf halbem Weg durch die Schleife enden.

Dies ist nicht unbedingt die effizienteste Technik oder diejenige, die den einfachsten regulären Ausdruck erzeugt, aber es ist einfach.

Gilles 'SO - hör auf böse zu sein'
quelle
3

Split q_1

Jukka Suomela
quelle
Und das beantwortet die Frage wie?
Raphael
1
Wenn Sie die Zustandsmaschine auf diese Weise neu schreiben, ist es jetzt trivial, den entsprechenden regulären Ausdruck zu lesen.
Jukka Suomela
1
Vielleicht sollten Sie dies in den Antworttext aufnehmen. Funktioniert das immer?
Raphael
@ Raphael: Es funktioniert in diesem Fall. :) Die allgemeine Idee hinter diesem Trick ist die folgende: Wir haben die Zyklen "richtig verschachtelt" gemacht. Das heißt, wir haben nicht die Zyklusstruktur [(])aber [()].
Jukka Suomela