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

26

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.

DW
fuente
Permítame dejar mi nota habitual: cuando proporcione una gramática libre de contexto para el idioma en cuestión, necesita una prueba de corrección que pueda hacer que el enfoque sea bastante difícil de manejar.
Raphael
En aras de hacer de esta una pregunta de referencia adecuada que podemos arrojar a los dumpers problemáticos, ¿podría agregar una respuesta sobre la creación de gramáticas y autómatas, tal vez con un ejemplo de cada uno? ¡Gracias!
Raphael
Hasta que el material se mueva aquí, tenga en cuenta que Rick Decker y babou recopilaron algunas expresiones idiomáticas sin contexto típicas en una pregunta duplicada .
Raphael

Respuestas:

13

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ónSS1S2

  2. unión: dividido en partes disjuntasSS1S2

  3. iteración: SS1Sε

Ejemplo 1

Aquí un ejemplo para la anidación (gracias Raphael).

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

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

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 .kok>o or k<ook>ok>ok=s+os>0sks+o

L1={bs+oal(bc)ma2lbol,m,o,sN,s>0,m2}

Algunas reescrituras simples.

L1={bbsboalbcbc(bc)m(aa)lbol,m,o,sN}

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í)S1TVTbUUbUε

(generamos o b 's en ambos lados)VbVbWo b

WaWaaX

, Y b c b c , Z b c Z εXYZYbcbcZbcZε

Ejemplo 2

K={akblcml=m+k}

Una primera reescritura "obvia".

K={akbm+kcmm,k0}={akbmbkcmm,k0}

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,mm+k=k+m

K={akbk+mcmm,k0}={akbkbmcmm,k0}

con producciones , X a X b ε , Y b Y c εSXYXaXbεYbYcε

De manera similar, K={akblcmm=k+l}={akblclckk,l0}

con producciones , X b X c εSaScXXbXcε


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).

Hendrik Jan
fuente
11

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 porTDT(TT^)TG=({S},TT^,δ,S)δ

.SaSa^Sε,aT

Teorema de Chomsky-Schützenberger

tiene contexto si y solo si hayLΣ

  • un alfabeto ,T
  • un lenguaje regular yR(TT^)
  • homomorfismo ψ:(TT^)Σ

así que eso

.L=ψ(DTR)

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 . ConL={anbncmn,mN

  • (y, canónicamente, T = { ] , } ),T={[,}T^={],}
  • yR=L([])
  • ψ(x)={a,x=[b,x= ]ε,x=c,x= 

el teorema implica que tiene contexto, en particular porqueL

.DTR={[n]nmmn,mN}

Ejemplo 2

Demuestre que tiene contexto.L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

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 . Usamosabcbbko

  • ,T={[,,,<}
  • yR=L(<+>+[++])L([++]<+>+)
  • ψ(x)={b,x{,,<}a,x=[aa,x= ]bc,x=ε,else

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 , obtenemosL=ψ(DTR)[]wDTR

DTR={<p>po[lmm]lop1,o0,l0,m2} {}

y con eso

ψ(DTR)={bp+oal(bc)ma2lbop1,o0,l0,m2} {}={bkal(bc)manbok,l,m,n,oN,k>o,2l=n,m2} {}=L.

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.DTRψ

  • 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).RDTψ

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!TRψ

Rafael
fuente
Es indecidible si algún idioma está libre de contexto.
reinierpost