Un estudiante me pidió lo siguiente y no pude encontrar una respuesta completa:
¿Existen propiedades de cierre para la clase de idiomas que no están libres de contexto?
Es bastante fácil encontrar ejemplos que muestren que no está cerrado bajo intersección e iteración (operador estrella de Kleene), pero ¿qué hay de la unión y la concatenación? Supongo que tampoco está cerrado, así que, a menos que esté lejos, lo que estoy buscando son ejemplos de dos no CFL en las que su unión o concatenación sea una CFL.
Respuestas:
Probablemente hay pocas o ninguna propiedad de cierre "interesante" y "natural" para la clase de lenguajes que no están libres de contexto. De hecho, eso probablemente sea cierto de:
cualquier clase de lenguajes que se define por un autómata específico, gramática o modelo computacional: los lenguajes regulares, los cfl's, varias subclases de los cfls como los lenguajes lineales y los cfl deterministas, los lenguajes sensibles al contexto, los lenguajes limitados y pronto.
La razón es que muchas, si no la mayoría, o todas las propiedades de cierre "interesantes" tienen la capacidad de simplificar drásticamente un lenguaje, por ejemplo, asignarlo a conjuntos finitos o algo igualmente simple. Por ejemplo, siempre puede aplicar un homomorfismo constante (h (a) = 0) a un lenguaje sin contexto y obtener el lenguaje de todas las cadenas de ceros, que es sin contexto (de hecho, regular). Entonces, si la definición misma de la clase implica que no es muy "simple" (como no libre de contexto), entonces el cierre lo lleva a lenguajes "simples", es decir, fuera de la clase.
En realidad, esto podría hacer un proyecto de investigación interesante, parte del cual, me arriesgaría a adivinar, sería definir "simple", "interesante" y "natural" de alguna manera adecuada, y también encontrar formas formales de tratar con asuntos triviales y triviales. casos degenerados como el que di.
fuente