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

25

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:

SaaSb
S

génère {a2ibi|i0} ,

SaSb
SaaSb
S

génère {aibjij0} , et

S b S b SSaSa
SbSb
S

génère , ou de manière équivalente { ( ( a | b ) ) 1 ( ( a | b ) ) 2p 1 = p R 2 } (où p 1 fait référence à la partie capturée par ( . . . ) 1{wwRw(a|b)}{((a|b))1((a|b))2p1=p2R}p1(...)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.aije>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?

Alex ten Brink
la source
3
Notez que l'ajout d'indices et de contraintes est trop puissant: vous pourrez définir , qui n'est pas un CFL. anbncn
Shaull

Réponses:

34

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

g::=ϵEmpty string|cCharacter c in alphabet Σ|ggConcatenation|Failing pattern|ggDisjunction|μα.gRecursive grammar expression|αExpression variable

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 μ α .μα.g .)gμα.ϵgα

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 αρΣ[ρ|α:L]ραLα .

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

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={w1w2|w1[[g1]]ρw2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNLnwhereL0=Ln+1=Ln[[g]][ρ|α:Ln]

En utilisant le théorème de Knaster-Tarski, il est facile de voir que l'interprétation de μα.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.

Neel Krishnaswami
la source
C'est assez génial. Y a-t-il un nom ou une référence standard pour cela?
Alex ten Brink
5
Arto Salomaa en parle dans son livre «Formal Languages» de 1973. Il les appelle «Regular-like Expressions».
Tim Schaeffer
3

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 .

μ

Jacques Carette
la source
μα.g[μα.g/α]g
1

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.

NinjaDarth
la source
4
Veuillez inclure toutes les informations pertinentes dans la réponse elle-même. «Regardez sous comp.compilers» est déjà une réponse peu utile, et elle sera complètement inutile dans quelques mois.
Emil Jeřábek soutient Monica
C'est totalement faux. Comp.compilers (contrairement à ce site et à d'autres blogs, soit dit en passant) est archivé en permanence. Vous y trouverez tous les détails dont vous avez besoin. Il existe également de nombreux liens dans le dernier article publié. De plus, contrairement aux sites de blog, il est ouvert sur l'extérieur et utile à un public beaucoup plus large. Vous ne devriez avoir aucune difficulté à trouver quoi que ce soit sur USENET - c'est là que des questions comme celle-ci doivent être traitées et discutées. Si vous avez des difficultés, voici le lien. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth
2
Le problème n'est pas qu'il n'est pas archivé, mais que les archives sont vastes. Quand je regarde les archives maintenant, je peux trouver votre message quelque part vers le haut, mais quand quelqu'un verra cette réponse dans quelques mois ou années dans le futur, il n'aura aucune idée où commencer à creuser. Il est arrogant et grossier de faire effectuer aux lecteurs une recherche longue et peu fiable lorsque vous pouvez les diriger vers un emplacement plus spécifique. Maintenant, je l'ai fait pour vous. Cela a pris environ 30 secondes. Vous auriez pu le faire vous-même.
Emil Jeřábek soutient Monica