Gibt es eine Erweiterung für reguläre Ausdrücke, die die kontextfreien Sprachen erfasst?

In vielen Arbeiten mit kontextfreien Grammatiken (CFGs) lassen die dort vorgestellten Beispiele für solche Grammatiken oft einfache Charakterisierungen der von ihnen erzeugten Sprache zu. Beispielsweise:

$S \to a a S b$
$S \to$

erzeugt ,$\{ a^{2i} b^i | i \geq 0\}$

$S \to a S b$
$S \to a a S b$
$S \to$

erzeugt$\{ a^i b^j \mid i \geq j \geq 0 \}$ und

$S \to a S a$
$S \to b S b$
$S \to$

erzeugt oder äquivalent (wobei sich auf den Teil bezieht, der von erfasst wurde ).$\{ w w^R \mid w \in (a|b)^* \}$$\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$$p_1$$(...)_1$

Die obigen Beispiele können alle durch Hinzufügen von Indizes ( ), einfachen Einschränkungen für diese Indizes ( ) und Musterübereinstimmung mit regulären Ausdrücken generiert werden . Ich frage mich daher, ob alle kontextfreien Sprachen durch eine Erweiterung der regulären Ausdrücke generiert werden können.$a^i$$i > j$

Gibt es eine Erweiterung von regulären Ausdrücken, die alle oder einige signifikante Teilmengen der kontextfreien Sprachen generieren können?

Ja da ist. Definieren Sie einen kontextfreien Ausdruck als einen Begriff, der von der folgenden Grammatik generiert wird:

$$\begin{array}{lcll} g & ::= & \epsilon & \mbox{Empty string}\\ & | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\ & | & g \cdot g & \mbox{Concatenation} \\ & | & \bot & \mbox{Failing pattern} \\ & | & g \vee g & \mbox{Disjunction}\\ & | & \mu \alpha.\; g & \mbox{Recursive grammar expression} \\ & | & \alpha & \mbox{Variable expression} \end{array}$$

Dies sind alle Konstruktoren für reguläre Sprachen mit Ausnahme von Kleene star, der durch einen allgemeinen Festkommaoperator und einen variablen Referenzmechanismus. (Der Kleene-Stern wird nicht benötigt, da er als g ∗ ≜ μ α definiert werden kann $\mu \alpha.\;g$ .)$g\ast \triangleq \mu \alpha.\;\epsilon \vee g\cdot\alpha$

Die Interpretation eines kontextfreien Ausdrucks erfordert die Berücksichtigung der Interpretation freier Variablen. So ein definieren Umgebung eine Karte von Variablen zu Sprachen (dh Teilmengen sein Σ * ), und lassen Sie [ ρ | α : L ] ist die Funktion, die sich bei allen Eingaben mit Ausnahme von α wie ρ verhält und die die Sprache L für α zurückgibt .$\rho$$\Sigma^*$$[\rho|\alpha:L]$$\rho$$\alpha$$L$$\alpha$

Definieren Sie nun die Interpretation eines kontextfreien Ausdrucks wie folgt:

$$\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}} \newcommand{\setof}[1]{\left\{#1\right\}} \newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}} \begin{array}{lcl} \interp{\epsilon}{\rho} & = & \setof{\epsilon} \\ \interp{c}{\rho} & = & \setof{c} \\ \interp{g_1\cdot g_2}{\rho} & = & \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\ \interp{\bot}{\rho} & = & \emptyset \\ \interp{g_1 \vee g_2}{\rho} & = & \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\ \interp{\alpha}{\rho} & = & \rho(\alpha) \\ \interp{\mu \alpha.\; g}{\rho} & = & \bigcup_{n \in \mathbb{N}} L_n \\ \mbox{where} & & \\ L_0 & = & \emptyset \\ L_{n+1} & = & L_n \cup \interp{g}{[\rho|\alpha:L_n]} \end{array}$$

Mit dem Knaster-Tarski-Theorem ist leicht zu erkennen, dass die Interpretation von ist das am wenigsten feste des Ausdrucks.$\mu \alpha.g$

Es ist einfach (wenn auch nicht ganz trivial) zu zeigen, dass Sie einen kontextfreien Ausdruck geben können, der dieselbe Sprache wie jede kontextfreie Grammatik hat, und umgekehrt. Die Nicht-Trivialität ergibt sich aus der Tatsache, dass kontextfreie Ausdrücke verschachtelte Fixpunkte haben und kontextfreie Grammatiken Ihnen einen einzelnen Fixpunkt über einem Tupel geben. Dies erfordert die Verwendung von Bekics Lemma, das genau besagt, dass ein verschachtelter Fixpunkt über ein Produkt in einen einzelnen Fixpunkt umgewandelt werden kann (und umgekehrt). Aber das ist die einzige Subtilität.

EDIT: Nein, ich kenne keine Standardreferenz dafür: Ich habe es für mein eigenes Interesse ausgearbeitet. Es ist jedoch offensichtlich genug, dass ich zuversichtlich bin, dass es zuvor erfunden wurde. Einige Gelegenheits-Googler enthüllen Joost Winter, Marcello Bonsangue und Jan Ruttens kürzlich erschienene Veröffentlichung Context-Free Languages, Coalgebraically , in der sie eine Variante dieser Definition angeben (wobei alle Fixpunkte geschützt werden müssen), die sie auch als kontextfreie Ausdrücke bezeichnen.

Zu MathOverflow gab es eine eng verwandte Frage (und mehrere Antworten) zu den Sprachen, deren generierende Funktionen holonom sind .

$\mu$

Wir haben kürzlich die Umrisse eines Frameworks veröffentlicht, das genau das ermöglicht. Schauen Sie unter comp.compilers nach , wo ich eine Benachrichtigung zusammen mit einigen Links gesendet habe.

Die neuen Entwicklungen stützen sich auf das Chomsky-Schützenberger-Theorem und können als Ergänzung dieses Ergebnisses angesehen werden. Chomsky selbst wurde über die Entwicklungen informiert und zeigt den Wunsch, "aufzuholen".

Zusammen mit dieser Entwicklung stellen wir auch die Äquivalenz von zwei getrennten Formulierungen für kontextfreie Ausdrücke fest - eine, die eine Erweiterung / Vervollständigung der Mu-Kalkülform "kleinster fester Punkt" darstellt (ursprünglich von Gruska, Yntema und McWhirter). die eine endgültige Formulierung von Art im Jahr 2014 erhalten - und die andere im Jahr 2008 veröffentlicht.