¿Construye todos los lenguajes sin contexto a partir de un conjunto de lenguajes base y propiedades de cierre?

10

Una forma de ver las expresiones regulares es como una prueba constructiva del siguiente hecho: es posible construir los idiomas regulares comenzando con un pequeño conjunto de idiomas y combinándolos a través de un pequeño conjunto fijo de propiedades de cierre. Específicamente, si comenzamos con el idioma vacío, el idioma que contiene la cadena vacía y los idiomas de todas las cadenas de un solo carácter, podemos ensamblar todos los idiomas regulares posibles usando unión, concatenación y estrella de Kleene.

¿Existe un conjunto de lenguajes base y propiedades de cierre que se pueden usar para generar todos los lenguajes sin contexto y solo ellos? (Para aclarar: no estoy preguntando si puedes escribir expresiones regulares para todas las CFL, lo cual sé que es imposible. En cambio, me pregunto si hay una manera de diseñar un marco similar a expresiones regulares para CFL basado en el mismos principios básicos).

templatetypedef
fuente
1
Mientras sucede, una de nuestras preguntas de referencia puede contener lo que necesita.
Raphael

Respuestas:

8

D2{[,],(,)}a1,b1,a2,b2

D2D2M(D2)

g(h1(D2)R)ghRRghD2

Lg(h1(L)R)g,h,R

Hendrik Jan
fuente
Wow, eso es realmente interesante! Si tiene alguna referencia sobre esto, ¡me encantaría consultarla!
templatetypedef
Fantástico. Esto responde perfectamente a mi pregunta.
templatetypedef