¿Los lenguajes libres de contexto en

20

Los lenguajes libres de contexto no están cerrados bajo complemento, lo sabemos.

Por lo que yo entiendo, los lenguajes sin contexto que son un subconjunto de unsi para algunas letras un,si están cerrados bajo el complemento (!?)

Aquí está mi argumento. Cada lenguaje CF L tiene una imagen Parikh semi-lineal π(L)={(metro,norte)unmetrosinorteL} . Los conjuntos semilineales están cerrados bajo complemento. El conjunto de vectores que representan el conjunto semi-lineal se puede transformar fácilmente en una gramática lineal.

Pregunta. ¿Existe una referencia fácilmente accesible a este hecho?

Técnicamente, estos lenguajes se denominan acotados , es decir, un subconjunto de w1...wk para algunas palabras w1,...,wk .

Mi motivación para esta pregunta es de una pregunta reciente sobre la libertad de contexto de {unnortesimetronorte2metro} . Su complemento dentro de unsi parece más fácil de manejar.

Hendrik Jan
fuente
¿Has visto "La teoría matemática de los lenguajes sin contexto" de Ginsburg? Aparentemente, el Teorema 5.4.2 da la caracterización de lenguajes libres de contexto limitados a los que te refieres, y apuesto a que Ginsburg mencionaría la implicación de complementar los lenguajes libres de contexto limitados (en el caso bidimensional).
Yuval Filmus

Respuestas:

12

Esta caracterización de los lenguajes libres de contexto limitados se debe a Ginsburg ("La teoría matemática de los lenguajes libres de contexto"), y aparece como Corolario 5.3.1 en su libro. Para general hay algunas restricciones en los conjuntos semilineales, pero para k 2 estas restricciones siempre se cumplen, por lo que es sencillo deducir que el complemento de dicho lenguaje (dentro de w 1 w 2 ) no tiene contexto .kk2w1w2

Ginsburg menciona estas implicaciones en su libro.

Corolario 5.6.1 Si y M 2 son lenguajes libres de contexto [], w 1 y w 2 palabras, entonces M 1M 2 es un lenguaje [libre de contexto].METRO1w1w2METRO2w1w2METRO1METRO2

Corolario 5.6.2 Si y M 2 son lenguajes libres de contexto [], w 1 y w 2 palabras, entonces M 1 - M 2 y M 2 - M 1 son [libre de contexto-] idiomasMETRO1w1w2METRO2w1w2METRO1-METRO2METRO2-METRO1

Yuval Filmus
fuente
2

Otra prueba utiliza la siguiente caracterización probada en esta respuesta :

El lenguaje tiene contexto si f es A definible en la aritmética de Presburger.{unyosij:(yo,j)UN}UN

Claramente, es definible en la aritmética de Presburger si f ¯ A es definible en la aritmética de Presburger.UNUN¯

Esto muestra que si los idiomas están libres de contexto, entonces todas las expresiones booleanas en los idiomas (que involucran unión, intersección y complementación) también están libres de contexto.Lyounsi

Yuval Filmus
fuente