Existe-t-il une extension des expressions régulières qui capture les langages sans contexte?

Dans de nombreux articles impliquant des grammaires sans contexte (CFG), les exemples de telles grammaires présentés ici admettent souvent des caractérisations faciles du langage qu'elles génèrent. Par exemple:

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

génère $\{ a^{2i} b^i | i \geq 0\}$ ,

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

génère $\{ a^i b^j \mid i \geq j \geq 0 \}$ , et

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

génère , ou de manière équivalente { ( ( a | b ) ∗ ) 1 ( ( a | b ) ∗ ) 2 ∣ p 1 = p R 2 } (où p 1 fait référence à la partie capturée par ( . . . ) $\{ w w^R \mid w \in (a|b)^* \}$$\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$$p_1$$(...)_1$ ).

Les exemples ci-dessus peuvent tous être générés en ajoutant des indices ( ), des contraintes simples sur ces indices ( i > j ) et une correspondance de motifs aux expressions régulières. Cela me fait me demander si tous les langages sans contexte peuvent être générés par une extension des expressions régulières.$a^i$$i > j$

Existe-t-il une extension d'expressions régulières qui peut générer la totalité ou une partie importante des langages sans contexte?

Oui il y a. Définissez une expression sans contexte comme un terme généré par la grammaire suivante:

$$\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}$$

Il s'agit de tous les constructeurs pour les langages réguliers, à l'exception de l'étoile de Kleene, qui est remplacée par un opérateur à virgule fixe général , et un mécanisme de référence variable. (L'étoile de Kleene n'est pas nécessaire, car elle peut être définie comme g ∗ ≜ μ α $\mu \alpha.\;g$ .)$g\ast \triangleq \mu \alpha.\;\epsilon \vee g\cdot\alpha$

L'interprétation d'une expression sans contexte nécessite de tenir compte de l'interprétation des variables libres. Définissez donc un environnement comme une carte des variables aux langages (c'est-à-dire des sous-ensembles de Σ ∗ ), et laissez [ ρ | α : L ] soit la fonction qui se comporte comme ρ sur toutes les entrées sauf α , et qui renvoie le langage L pour $\rho$$\Sigma^*$$[\rho|\alpha:L]$$\rho$$\alpha$$L$$\alpha$ .

Maintenant, définissez l'interprétation d'une expression hors contexte comme suit:

$$\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}$$

En utilisant le théorème de Knaster-Tarski, il est facile de voir que l'interprétation de $\mu \alpha.g$ est la moins fixe de l'expression.

Il est simple (bien que pas entièrement trivial) de montrer que vous pouvez donner une expression sans contexte dérivant le même langage que n'importe quelle grammaire sans contexte, et vice-versa. La non-trivialité vient du fait que les expressions sans contexte ont des points fixes imbriqués et que les grammaires sans contexte vous donnent un seul point fixe sur un tuple. Cela nécessite l'utilisation du lemme de Bekic, qui dit précisément qu'un point fixe imbriqué peut être converti en un seul point fixe sur un produit (et vice-versa). Mais c'est la seule subtilité.

EDIT: Non, je ne connais pas de référence standard pour cela: je l'ai élaboré pour mon propre intérêt. Cependant, c'est une construction suffisamment évidente pour être sûre qu'elle a déjà été inventée. Des recherches occasionnelles sur Google révèlent Joost Winter, Marcello Bonsangue et le récent article Context-Free Languages, Coalgebraically de Jan Rutten , où elles donnent une variante de cette définition (exigeant que tous les points fixes soient gardés) qu'ils appellent également des expressions sans contexte.

Il y avait une question étroitement liée (et plusieurs réponses) sur MathOverflow au sujet des langages dont les fonctions de génération sont holonomiques .

$\mu$

Nous avons récemment publié les grandes lignes d'un cadre qui fera exactement cela. Regarder sous comp.compilers , où j'ai envoyé une notification avec quelques liens.

Les nouveaux développements fonctionnent à partir du théorème de Chomsky-Schuetzenberger et peuvent être considérés comme l'achèvement de ce résultat. Chomsky, lui-même, a été informé des développements et indique un désir de «rattraper son retard».

Parallèlement à ce développement, nous établissons également l'équivalence de deux formulations distinctes pour les expressions sans contexte - l'une qui est une extension / complétion de la forme de mu-calcul du «point le moins fixe» (à l'origine par Gruska, Yntema et McWhirter) - qui a reçu une sorte de formulation finale en 2014 - et l'autre publié en 2008.