Algorithmus für reguläre Ausdrücke Kreuzung mit cfg

Question

suchen Im für einen Algorithmus, der ausgibt, wenn der Schnittpunkt eines regulären Ausdrucks und einer contex freie Grammatik leer ist oder nicht. Ich weiß, dass dieses Problem entscheidbar ist, ich aber keine Beispielimplementierung finden (in Pseudo-Code).

Kann jemand geben mir einen solchen Algorithmus, in .NET, wenn möglich, aber das ist kein Muss. Dieses Problem wird auch „normale Kreuzung“ bezeichnet. denn es googeln es gibt mir nur die geometrischen Algorithmus oder die Theorie über.

Bearbeiten :

Jeder. Im wirklich drauf stecken und kann noch nichts finden.

Answer 1

Hier ist eine Skizze eines Ansatzes, die mir einfällt. Ich denke, das sollte funktionieren, aber es ist wahrscheinlich nicht der beste Weg, es zu tun, da es die schrecklich unordentlich Umwandlung von PDA zu CFG verwendet.

Konvertieren des regulären Ausdrucks in einen nichtdeterministischen endlichen Automaten (NFA) und reduziert bis auf die minimalen determinsitic endlichen Automaten (DFA). Konvertieren Sie die kontextfreie Grammatik (CFG) in einen Keller automoton (PDA). Diese ersten Schritte sind alle gut bekannt und ziemlich einfache Algorithmen.

Nehmen Sie die Kreuzung des EDA und PDA, die auch ein PDA ist. Wir werden sagen, der DFA Zustände S1 hat, Zustand S1 starten, Endzustände F1 und Übergänge delta1 der Form ((Quelle, trigger), Ziel) und der PDA S2 wurde Staaten, Startzustand s2, Endzustände F2 und Transitionen Delta2 der Form ((Quelle, Trigger, pop), (destination, push)). Der neue PDA hat Zustände S1 S2 X, wobei jeder Zustand durch ein Paar etikettiert. Es hat Endzustände F1 X F2 und Startzustand (s1, s2). Jetzt für die Übergänge.

Für jeden Übergang D ein Element der delta2 für jeden Zustand ein Element s1 s, finden den Übergang t ein Element der delta1 der Form ((s, d.trigger) ,?). Machen Sie einen neuen Übergang (((d.source, s), d.trigger, d.pop), ((d.destination, t.destination), d.push)).

Das neue PDA soll die Kreuzung der Sprachen produziert von der RE und dem CFG akzeptieren. Um zu testen ob die Sprache ist leer Sie es benötigen, um zu einem CFG konvertieren zurück. Der Algorithmus für das ist chaotisch und groß, aber es funktioniert. Sobald Sie das getan haben, jedes Terminal-Symbol markieren. Dann jedes Symbol markiert, die eine Regel hat, wo es nur Symbole auf der rechten Seite markiert, und wiederholen Sie, bis Sie nicht mehr Symbole markieren können. Wenn Sie das Startsymbol markieren, ist die Sprache nicht leer. Andernfalls wird die Sprache ist leer.