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).
fuente
Respuestas:
fuente