Définir l' équivalence de Nérode sur une langue$L \subseteq \Sigma^{*}$ comme $u \sim_L v$ ssi $uw \in L \Leftrightarrow vw \in L$ pour chaque $w \in \Sigma^{*}$.

L'équivalence Nerode ${\sim}_L$ a un nombre fini de classes d'équivalence précisément lorsque $L$peut être reconnu par un automate à états finis. C'est le théorème de Myhill-Nerode .

Existe-t-il une caractérisation similaire des langues sans contexte?

Motivation:

Les classes d'équivalence Nerode correspondent chacune à un état distinct dans tout automate qui reconnaît $L$. Chaque LFC peut être reconnue par un NPDA, qui a un nombre fini d'états mais aussi une pile potentiellement illimitée de symboles alphabétiques. La pile conserve une trace d'une manière possible d'analyser une chaîne. Le nombre de classes d'équivalence peut être infini car la pile peut stocker un nombre illimité de symboles.

Je demande: existe-t-il toujours un moyen de regrouper les classes d'équivalence afin que chaque groupe représente un état du PDA, chaque classe du groupe représentant des états équivalents de la pile pour cet état PDA?

Par exemple, le langage des parenthèses correctement imbriquées n'a besoin que d'états à gérer popet push, comme la pile gardera une trace de la profondeur d'imbrication actuelle. Si un tel agrégat peut toujours être fait, alors si le nombre d'agrégats est fini détermine si le langage est hors contexte.

Comme l'a souligné @sdcvvc dans un commentaire, une forme de cette question a été posée sous la forme /math/118362, bien que la réponse de Yuval Filmus à la question connexe à l' exemple d'un langage sans contexte qui, néanmoins, PEUT être pompé? est plus pertinent.

David S. Wise fournit dans son article Un fort lemme de pompage pour les langues sans contexte un lemme de pompage fort qui équivaut à être sans contexte. Il fournit également une condition équivalente supplémentaire (propriété 3 à la page 362) qui, selon lui, pourrait être considérée comme un analogue du théorème de Myhill-Nerode. En application de ce dernier, il montre que$\{ a^nba^{mn} : m,n > 0 \}$ ne peut pas être exprimé comme une intersection finie de langages sans contexte.

Plus d'informations sur le lemme de pompage fort apparaissent dans l' une de mes réponses .

Il y a une très belle caractérisation des langages hors contexte (attribuée à Wechler) dans l'article de Berstel et Boasson, Vers une théorie algébrique des langages hors contexte . Permettez-moi d'introduire quelques définitions afin d'énoncer ce résultat (Théorème 3.1 dans l'article).

La fermeture polynomiale $Pol(\mathcal{L})$ d'une classe $\mathcal{L}$ des langues de $A^*$ est l'ensemble de toutes les langues qui sont des unions finies de produits de la forme $L_0a_1L_1 \dotsm a_nL_n$, où $L_0, ..., L_n \in \mathcal{L}$ et $a_1, ..., a_n \in A$.

Une algèbre est une classe$\mathcal{A}$ des langues contenant la langue $\{1\}$ et tel que $\mathcal{A} = Pol(\mathcal{A})$. Il est généré de manière finie si$\mathcal{A} = Pol(\mathcal{F})$ pour un ensemble fini $\mathcal{F}$des langues. Il est stable si, pour chaque$L \in \mathcal{A}$ et $u \in A^*$, la langue $u^{-1}L = \{v \mid uv \in L\}$ appartient également à $\mathcal{A}$. Notez qu'il suffit d'avoir$a^{-1}L \in \mathcal{A}$ pour tous $a \in A$.

Théorème . Une langue de$A^*$ est sans contexte si et seulement s'il appartient à une algèbre stable générée de manière finie.

Voir l'article pour des exemples éclairants et de nombreuses belles conséquences.