Welche Algorithmen gibt es für die Erstellung eines DFA, der die von einem bestimmten regulären Ausdruck beschriebene Sprache erkennt?

11

Alle meine Lehrbücher verwenden denselben Algorithmus zum Erstellen eines DFA mit einem regulären Ausdruck: Erstellen Sie zuerst einen NFA, der die Sprache des regulären Ausdrucks erkennt, und konvertieren Sie dann den NFA mithilfe der Teilmengenkonstruktion (auch als "Powerset" bezeichnet) in einen äquivalenten DFA ( optional Minimierung des DFA). Ich hörte auch einmal einen Professor darauf hinweisen, dass es andere Algorithmen gibt. Kennt jemand welche? Vielleicht eine, die direkt vom regulären Ausdruck zu einem DFA ohne die Zwischen-NFA geht?

BlueBomber
quelle
Willkommen bei cstheory, einer Q & A-Site für Fragen auf Forschungsebene in der theoretischen Informatik (TCS). Ihre Frage scheint in TCS keine Frage auf Forschungsebene zu sein. Weitere Informationen dazu finden Sie in den FAQ . Ihre Frage ist möglicherweise für die Informatik geeignet, die einen breiteren Anwendungsbereich hat.
Kaveh
1
Warum verwenden Sie diesen Vorlagenkommentar immer ? Anscheinend gibt es mindestens 5, die Ihnen nicht zustimmen. Ich würde vorschlagen, dass Sie solchen Fragen eine Chance geben.
AJed
@ Ajed, ich benutze diesen Kommentar nicht immer . Ich benutze es, wenn mir eine Frage nicht zum Thema gehört, aber für die Informatik geeignet sein könnte . Up Votes bedeuten nicht, dass eine Frage zum Thema gehört, und diese Frage scheint mir keine Frage auf Forschungsebene zu sein, daher halte ich den Kommentar für angemessen. (Die Tatsache, dass jemand eine Antwort auf Forschungsebene auf eine Frage schreiben kann, macht die Frage nicht zu einer Forschungsebene.) Ps: Ich denke, diese Diskussion ist besser für Theoretical Computer Science Meta geeignet .
Kaveh

Antworten:

13

Es gibt verschiedene Algorithmen, um reguläre Ausdrücke in endliche Automaten umzuwandeln. Sie können direkt von regulären Ausdrücken zu DFAs wechseln, ohne zuerst einen anderen Automaten zu erstellen, indem Sie implizit die Teilmengenkonstruktion ausführen, während Sie den Automaten generieren. Eine andere Möglichkeit, deterministische Automaten direkt zu erhalten, ist die Verwendung der Methode der Derivate.

Die Überprüfung, ob ein regulärer Ausdruck die Sprache darstellt, die alle Zeichenfolgen enthält, ist ein vollständiges PSPACE-Problem ( eine Referenz finden Sie in dieser Antwort ). Wenn Sie überprüfen, ob ein DFA diese Sprache akzeptiert, kann dies in Polynomzeit erfolgen. Wenn Sie also direkt von einem regulären Ausdruck zu einem DFA wechseln, kommt es irgendwo zu einer Explosion.

Mein Verständnis der Literatur ist, dass wir Übersetzungen auswählen können, die es uns ermöglichen, die Explosion zu lokalisieren. Das heißt, es gibt verschiedene Wege, um von einem regulären Ausdruck zu einem endlichen Automaten zu gelangen, und Methoden, die linear oder polynomisch sind, werden bevorzugt. Normalerweise werden die exponentiellen Kosten in die Bestimmung von Automaten hineingeschoben.

Es wurde viel daran gearbeitet, Unterfamilien regulärer Ausdrücke zu identifizieren, aus denen wir effizient DFAs generieren können. Diese Arbeit hängt von der von Ihnen verwendeten Übersetzung ab. Das heißt, Sie korrigieren eine Zuordnung von regulären Ausdrücken zu NFAs und versuchen, die regulären Ausdrücke zu charakterisieren, die DFAs zugeordnet sind.

Die Standardkonstruktion von Automaten aus regulären Ausdrücken ist bei solchen Arbeiten nicht die bevorzugte Konstruktion . Die Konstruktionen der Wahl erzeugen Automaten, die der Struktur des regulären Ausdrucks sehr ähnlich sind. Diese Konstruktionen verwenden den Begriff einer Ableitung eines regulären Ausdrucks.

Derivate regulärer Ausdrücke , JA Brzozowski. 1964.

srara

Partielle Ableitungen regulärer Ausdrücke und endlicher Automatenkonstruktionen , V. Antimirov. 1995.

Wenn Sie sich einen Zustand eines Automaten als Darstellung aller von diesem Zustand akzeptierten Zeichenfolgen vorstellen, können Sie mit (Teil-) Ableitungen reguläre Ausdrücke als Zustände behandeln . Im Gegensatz zur Standard-Lehrbuchkonstruktion, bei der reguläre Ausdrücke intuitiv als Automaten und nicht als Zustände behandelt werden.

Von regulären Ausdrücken zu deterministischen Automaten , G. Berry und R. Sethi, 1986.

Die Entsprechung zwischen regulären Ausdrücken und Zuständen eines Automaten und Determinismus wird explizit von Berry und Sethi diskutiert, die den Begriff der Brzozowski-Derivate mit der Idee kombinieren, zwischen Vorkommen desselben Symbols zu unterscheiden, um eine syntaxbasierte Übersetzung regulärer Ausdrücke in endliche zu erhalten Automaten.

Eindeutige reguläre Sprachen , A. Brüggemann-Klein und Derick Wood, 1998.

Dieses Papier baut auf früheren Arbeiten von Brüggemann-Klein auf und untersucht Fälle, in denen Sie Derivate verwenden können, um DFAs in Polynomzeit zu generieren. Es gibt eine Menge Arbeit nach diesem Papier. Aus Sicht der Webtechnologien war dies von Bedeutung, da reguläre Ausdrücke, die effizient manipuliert werden können (auch bekannt als DFAs), für die Verarbeitung von SGML und XML wichtig waren.

Es wurde viel gearbeitet, um andere Sonderfälle deterministischer regulärer Ausdrücke zu untersuchen. Eine kürzlich erschienene Arbeit, die untersucht, wann einige dieser Probleme in linearer Zeit gelöst werden können, stammt aus dem Jahr 2012.

Deterministische reguläre Ausdrücke in linearer Zeit , Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.

Vijay D.
quelle
5
Sie haben in Ihrer Antwort bereits Derivate erwähnt, daher sollten Sie auch JA Brzozowski hinzufügen: Derivate regulärer Ausdrücke, Journal of the ACM 11 (4): 481–494 (1964), da er einen direkten Algorithmus für die Konvertierung von regulären Ausdrücken in DFAs angibt .
Neel Krishnaswami
3
Ich habe darüber diskutiert. Aber alle drei oben genannten Artikel bauen direkt auf diesem Ergebnis auf, und ich dachte, es gäbe keinen Grund, es zu erwähnen. Auch das Papier von Brueggeman-Klein und Wood ist voller Beispiele. Wenn ich Brzozowski erwähne, sollte auch Antimirov erwähnt werden. Ich wollte eine Umfrage vermeiden, aber vielleicht sollte ich es einfach machen. Was sagen?
Vijay D
5
Wenn Sie Zeit und Energie haben, denke ich, dass längere umfrageähnliche Antworten hier sehr angemessen sind.
David Eppstein
1
@ VijayD: Ja, ich stimme David zu. Kurze Antworten sind in Ordnung, aber wenn Sie die Energie haben, ist es schön, eine umfassende Antwort zu geben.
Neel Krishnaswami