Wie konvertiere ich eine nicht einbettende kontextfreie Grammatik in eine reguläre Grammatik?

Bitte beachten Sie, dass mir die Unentscheidbarkeit der Umwandlung von kontextfreier Grammatik in reguläre Grammatik bekannt ist. Aber gibt es angesichts der nicht einbettenden Eigenschaft der kontextfreien Eingabegrammatik einen Algorithmus, um sie direkt in reguläre Grammatik oder DFA umzuwandeln?

Schauen Sie sich diesen Link an . Dies ist eine einfachere Version eines Beweises von Chomsky, dass NSE-Grammatiken reguläre Sprachen darstellen. Glücklicherweise zeigt die Proof-Technik, wie aus einer gegebenen NSE-Grammatik eine linksreguläre Grammatik konstruiert wird. Hier ist meine Erklärung:

1. für jedes der Paare von Elementen von anhand der angegebenen Definition , ob : wenn .$\lvert V \rvert (\lvert V \rvert +1)/2$$(v_1, v_2)$$V$$v_1 \le v_2$$v_1 \le v_2$$v_2 *:= V^* v_1 V^*$
2. Construct Äquivalenzklassen , so dass , wenn und , und in der gleichen Äquivalenzklasse sind. Dies ist eine Aufteilung aller Elemente von in eine oder mehrere Äquivalenzklassen.$v_1 \le v_2$$v_2 \le v_1$$v_1$$v_2$$V$
3. nun für jedes Paar von Äquivalenzklassen von wie oben beschrieben, ob indem Sie prüfen, ob in in .$(VE_1, VE_2)$$V$$VE_1 \le VE_2$$v_1$$VE_1 \le v_2$$VE_2$
4. Konstrukt setzt , die den Äquivalenzklassen entsprechen, so dass, wenn , eine Teilmenge von . Jedes muss auch den Alphabetsatz . Sie haben ein für jedes , und jedes enthält zusätzlich zu allen Alphabetsymbolen Variablen in Äquivalenzklassen, die "kleiner als" das entsprechende sind.$UE$$VE$$VE_i \le VE_k$$VE_i$$UE_k$$UE_k$$E$$UE$$VE$$UE$$VE$
5. Bestimmen Sie für jede Variable wie folgt: ist die Menge aller Produktionen in deren linke Seite zur Äquivalenzklasse gehört, die die Variable .$P(v)$$v$$P(v)$$P$$v$
6. Konstruieren Sie für jede Variable eine Grammatik wie folgt: , wobei die Äquivalenzklasse ist, die und das diejenige ist, die dem .$v$$G(v) = (VE \cup UE, UE, P(v), v)$$VE$$v$$UE$$VE$
7. Die Autoren haben ein Lemma bewiesen, das behauptet, dass eine lineare Grammatik ist. Daraus können wir für jede Variable reguläre Ausdrücke über schreiben . Beachten Sie, dass dieser reguläre Ausdruck für das , das dem "kleinsten" , nur Symbole aus dem ursprünglichen Alphabet .$G(v)$$UE$$v$$UE$$VE$$E$
8. Ersetzen Sie reguläre Ausdrücke, die nur Alphabetsymbole enthalten, iterativ durch kompliziertere reguläre Ausdrücke aus Schritt 7. Schließlich erhalten Sie einen regulären Ausdruck, der der Sprache entspricht, die aus dem ursprünglichen Startsymbol generiert wurde , und dieser reguläre Ausdruck enthält nur Alphabetsymbole aus dem Original Alphabet.$S$
9. Sie haben jetzt einen regulären Ausdruck für die NSE-Grammatik und können mithilfe des Kleene-Theorems, der Teilmengenkonstruktion und eines DFA-Minimierungsalgorithmus einen minimalen DFA erhalten.

Wenn Sie ein Beispiel wünschen, kann ich später versuchen, eines bereitzustellen. Versuchen Sie, ein paar selbst zu machen, lesen Sie das Papier (es ist kurz), und wir können später über Komplexität sprechen.