¿Cómo demostrar que un idioma no tiene contexto?

Existen muchas técnicas para demostrar que un idioma no está libre de contexto, pero ¿cómo pruebo que un idioma no tiene contexto?

¿Qué técnicas hay para probar esto? Obviamente, una forma es exhibir una gramática libre de contexto para el lenguaje. ¿Existen técnicas sistemáticas para encontrar una gramática libre de contexto para un idioma dado?

Para los lenguajes regulares, no son formas sistemáticas para derivar un autómata regular de la gramática / de estado finito: por ejemplo, el Myhill-Nerode teorema proporciona una manera. ¿Existe alguna técnica correspondiente para los lenguajes sin contexto?

Mi motivación aquí es (con suerte) construir una pregunta de referencia que contenga una lista de técnicas que a menudo son útiles, cuando intento demostrar que un idioma dado no tiene contexto. Dado que tenemos muchas preguntas aquí que son casos especiales de esto, sería bueno si pudiéramos documentar el enfoque general o las técnicas generales que uno puede usar para enfrentar este tipo de problema.

Un enfoque práctico que en muchos ejemplos funciona [pero no siempre lo sé] está tratando de encontrar la estructura de anidación de las cadenas en el lenguaje. Las "dependencias anidadas" deben generarse al mismo tiempo en diferentes partes de la cadena.

También tenemos la caja de herramientas básica :

1. concatenación: si puedes dividir el idioma en dos partes consecutivas usa esta producción$S\to S_1S_2$

2. unión: dividido en partes disjuntas$S\to S_1 \mid S_2$

3. iteración: $S\to S_1S \mid \varepsilon$

Ejemplo 1

Aquí un ejemplo para la anidación (gracias 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 \}$

Reemplace por 2 l . Ahora podemos soltar n en condiciones.$n$$2l$$n$

Reemplace por k > o  o  k < o (¿confundido? O es 'oh' no 'cero'). Aplicar herramientas para la unión. Trabajamos con k > o aquí. También k > o iff k = s + o y s > 0 donde s es una nueva variable. Reemplace k por s + o .$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 \}$

Algunas reescrituras simples.

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

Ahora vemos la estructura de anidación y comenzamos a construir una gramática.

, T → b U , U → b U ∣ ε (ver: concatenación e iteración aquí)$S_1 \to TV$$T\to bU$$U\to bU \mid \varepsilon$

(generamos o b 's en ambos lados)$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$

Ejemplo 2

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

Una primera reescritura "obvia".

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

En lingüística, esto se denomina "dependencia de serie cruzada": el entrelazado (generalmente) indica fuertemente la ausencia de contexto. Por supuesto, m + k = k + my estamos salvados.$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\}$

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

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

con producciones , X → b X c ∣ $S\to aSc \mid X$$X\to bXc\mid \varepsilon$

Comentario final: estas técnicas lo ayudan a encontrar una gramática libre de contexto que, con suerte, reconocerá su idioma. Es posible que aún se necesite una prueba de corrección para garantizar que la gramática realmente funcione para reconocer su idioma (nada más y nada menos).

Hay una caracterización de CFL que puede ser útil, el teorema de Chomsky-Schützenberger .

Lenguaje Dyck

Deje un alfabeto. Definimos el Dyck -language D T ⊆ ( T ∪ T ) * de T por el contexto de libre gramática G = ( { S } , T ∪ T , δ , S ) con δ dado por$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$

Teorema de Chomsky-Schützenberger

tiene contexto si y solo si hay$L \subseteq \Sigma^*$

• un alfabeto ,$T$
• un lenguaje regular y$R \subseteq (T \cup \hat{T})^*$
• homomorfismo $\psi : (T \cup \hat{T}) \to \Sigma^*$

así que eso

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

Tenga en cuenta que el homomorfismo se extiende a las palabras (símbolo por símbolo) y luego a los idiomas (palabra por palabra).

Ejemplo

Considere . Con$L = \{ a^n b^n c^m \mid n,m \in \mathbb{N}$

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

el teorema implica que tiene contexto, en particular porque$L$

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

Ejemplo 2

Demuestre que tiene contexto.$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 \}$

Aquí, necesitamos un tipo de paréntesis para , uno para b c , uno para b y otro para modelar el b que causa k ≠ o . Usamos$a$$bc$$b$$b$$k \neq o$

• ,$T = \{ [, \langle, \vdash, < \}$
• y$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}$

y aplica el teorema. Con el fin de ver que , que no necesitamos más que el hecho de que los símbolos coincidentes (por ejemplo, [ y ] ) tienen que ocurrir con la misma frecuencia en cualquier w ∈ D T . Agregando esta restricción a las expresiones regulares por las que definimos R , obtenemos$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*}$

y con eso

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

A gramáticas y autómatas

Si queremos tener un autómata o gramática al final, tenemos más trabajo por delante.

• Hacia un autómata, construir el NPDA para y un NFA para R . El primero es estándar y tenemos algoritmos para el segundo, siempre que el lenguaje se proporcione en una representación adecuada (ver también aquí ). La intersección de ambos es otra construcción estándar y ψ se puede aplicar a cada transición individualmente.$D_T$$R$$\psi$

• Hacia una gramática, construya uno para (nuevamente, debería ser estándar), tome el de D T e intersectalos . Luego aplique ψ al conjunto de reglas (símbolo por símbolo).$R$$D_T$$\psi$

Podría decirse que esto es fácil ya que algorítmico; la complejidad radica en encontrar adecuada , R y ψ . No sé si este enfoque es (a menudo) más simple que construir PDA / gramáticas directamente, pero puede permitir centrarse en las características importantes del lenguaje en cuestión. Prueba por ti mismo!$T$$R$$\psi$