Comment prouver qu'une langue est hors contexte?

Il existe de nombreuses techniques pour prouver qu'une langue n'est pas sans contexte, mais comment puis-je prouver qu'une langue est sans contexte?

Quelles techniques existe-t-il pour le prouver? De toute évidence, une façon consiste à présenter une grammaire sans contexte pour la langue. Existe-t-il des techniques systématiques pour trouver une grammaire sans contexte pour une langue donnée?

Pour les langages réguliers, il existe des moyens systématiques de dériver un automate grammatical / à états finis: par exemple, le théorème de Myhill-Nerode fournit un moyen. Existe-t-il une technique correspondante pour les langages hors contexte?

Ma motivation ici est (espérons-le) de construire une question de référence qui contient une liste de techniques qui sont souvent utiles, lorsque j'essaie de prouver qu'une langue donnée est hors contexte. Puisque nous avons ici de nombreuses questions qui en sont des cas particuliers, il serait bien que nous puissions documenter l'approche générale ou les techniques générales que l'on peut utiliser face à ce type de problème.

Une approche pratique qui, dans de nombreux exemples, fonctionne [mais pas toujours, je sais] essaie de trouver la structure d'imbrication des chaînes dans le langage. Les "dépendances imbriquées" doivent être générées en même temps dans différentes parties de la chaîne.

Nous avons également la boîte à outils de base :

1. concaténation: si vous pouvez diviser la langue en deux parties consécutives utilisez cette production$S\to S_1S_2$

2. union: divisé en parties disjointes$S\to S_1 \mid S_2$

3. itération:$S\to S_1S \mid \varepsilon$

Exemple 1

Voici un exemple pour la nidification (merci Raphael).

$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$

Remplacez par . Nous pouvons maintenant déposer dans des conditions.$n$$2l$$n$

Remplacez par (confus? est «oh» et non «zéro»). Appliquer des outils pour l'union. Nous travaillons avec ici. Aussi ssi k = s + o et s > 0 où s est une nouvelle variable. Remplacez k par s + o .k > o  ou  k < o o k > o k > $k \neq o$$k > o \text{ or } k < o$$o$$k > o$$k>o$$k=s+o$$s>0$$s$$k$$s+o$

$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$

Quelques réécritures simples.

$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N} \}$

Nous voyons maintenant la structure d'imbrication et commençons à construire une grammaire.

, T → b U , U → b U ∣ ε (voir: concaténation et itération ici)$S_1 \to TV$$T\to bU$$U\to bU \mid \varepsilon$

(nous générons des o b des deux côtés)$V \to bVb \mid W$$o$ $b$

$W \to aWaa\mid X$

, Y → b c b c , Z → b c Z ∣ $X\to YZ$$Y\to bcbc$$Z\to bcZ\mid \varepsilon$

Exemple 2

$K =\{ a^kb^lc^m \mid l=m+k\}$

Une première réécriture "évidente".

$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$

Dans le linguistice, cela s'appelle la «dépendance inter-série»: l'entrelacement (généralement) indique fortement l'absence de non-contexte. Bien sûr, m + k = k + m et nous sommes sauvés.$k,m,k,m$$m+k=k+m$

$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$

avec productions , X → a X b ∣ ε , Y → b Y c ∣ $S\to XY$$X\to aXb\mid \varepsilon$$Y\to bYc\mid \varepsilon$

De même $K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$

avec productions , X → b X c ∣ $S\to aSc \mid X$$X\to bXc\mid \varepsilon$

Commentaire final: ces techniques vous aident à trouver une grammaire sans contexte candidate qui, nous l'espérons, reconnaîtra votre langue. Une preuve d'exactitude peut encore être nécessaire, pour garantir que la grammaire fonctionne vraiment pour reconnaître votre langue (ni plus ni moins).

Il existe une caractérisation des CFL qui peut être utile, le théorème de Chomsky-Schützenberger .

Langue Dyck

Soit un alphabet. Nous définissons le Dyck -language D T ⊆ ( T ∪ T ) * de T par le libre contexte grammaire G = ( { S } , T ∪ T , δ , S ) avec δ donné par$T$$D_T \subseteq (T \cup \hat{T})^*$$T$$G = (\{S\}, T \cup \hat{T}, \delta, S)$$\delta$

.$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad a \in T$

Théorème de Chomsky-Schützenberger

est hors contexte si et seulement s'il y a$L \subseteq \Sigma^*$

• un alphabet ,$T$
• une langue régulière et$R \subseteq (T \cup \hat{T})^*$
• homomorphisme $\psi : (T \cup \hat{T}) \to \Sigma^*$

pour que

.$\qquad \displaystyle L = \psi(D_T \cap R)$

Notez que l'homomorphisme est étendu aux mots (symbole par symbole) puis aux langues (mot par mot).

Exemple

Considérons . Avec$L = \{ a^n b^n c^m \mid n,m \in \mathbb{N}$

• (et, canoniquement, T = { ] , ⟩ } ),$T = \{ [, \langle\}$$\hat{T} = \{ ], \rangle\}$
• et$R = \mathcal{L}([^* ]^*\langle^* \rangle^*)$
• $\psi(x) = \begin{cases} a, &x = [ \\ b, &x =\ ] \\ \varepsilon, &x = \langle \\ c, &x =\ \rangle \end{cases}$

le théorème implique que est sans contexte, en particulier depuis$L$

.$\qquad\displaystyle D_T \cap R = \{[^n ]^n \langle^m \rangle^m \mid n,m \in \mathbb{N}\}$

Exemple 2

Montrer que est sans contexte.$L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \neq o, 2l = n, m \geq 2 \}$

Ici, nous avons besoin d'un type de parenthèses pour , une pour b c , une pour b et une autre utilisée pour modéliser les b qui causent k ≠ o . Nous utilisons$a$$bc$$b$$b$$k \neq o$

• ,$T = \{ [, \langle, \vdash, < \}$
• et$R = \mathcal{L}(<^+>^+\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*) \cup \mathcal{L}(\vdash^* [^* \langle\langle^+ \rangle^+\rangle ]^* \dashv^*<^+>^+)$
• $\psi(x) = \begin{cases} b, &x \in \{\vdash, \dashv, <\} \\ a, &x = [ \\ aa, &x =\ ] \\ bc, &x = \langle \\ \varepsilon, &\text{else} \end{cases}$

et appliquer le théorème. Pour voir que , nous ne devons plus que le fait que les symboles correspondants (par exemple , [ et ] ) doivent se produire aussi souvent en tout w ∈ D T . En ajoutant cette contraint aux expressions régulières que nous avons définies R par, nous obtenons$L = \psi(D_T \cap R)$$[$$]$$w \in D_T$$R$

$\qquad \begin{align*} D_T \cap R = &\{<^p>^p \vdash^o [^l \langle^m \rangle^m ]^l \dashv^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2\} \\ &\cup\ \{\dots\} \end{align*}$

et avec cela

$\qquad\begin{align*} \psi(D_T \cap R) &= \{ b^{p+o} a^l (bc)^m a^{2l} b^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2 \} \\ &\quad \cup\ \{ \dots \} \\ &= \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k > o, 2l = n, m \geq 2 \} \\&\quad \cup\ \{ \dots \} \\ &= L \;. \end{align*}$

To grammars and automata

If we want to have an automaton or grammar in the end, we have some more work ahead of us.

• Towards an automaton, construct the NPDA for $D_T$ and an NFA for $R$. The former is standard and we have algorithms for the latter, provided the language is given in a suitable representation (see also here). Intersection both is another standard construction and $\psi$ can be applied to every transition individually.

• Towards a grammar, build one for $R$ (again, should be standard), take the one for $D_T$ and intersect them. Then apply $\psi$ to the rule set (symbol for symbol).

Arguably, this is easy since algorithmic; the complexity lies in finding suitable $T$, $R$ and $\psi$. I don't know if this approach is (often) simpler than constructing PDA/grammars directly but it may allow to focus on the important features of the language at hand. Try for yourself!