¿Por qué existen dos tipos de lenguajes? Hasta este momento hemos establecido que existen dos tipos de lenguajes: los Lenguajes Regulares (LR) están asociados a los autómatas finitos y Lenguajes Libres de Contexto (LLC) están asociados a las Gramáticas Libres de Contexto (GLC). En interesante notar, que mientras los LLC no pueden ser aceptados por automátas finitos, los LR si pueden ser generados por una gramática. Por ejemplo, la siguiente gramática genera las cadenas con número par de bes:
\(\begin{array}{rl} S & \rightarrow aS | \rightarrow bB | \varepsilon \\ B & \rightarrow aS | \rightarrow bS \\ \end{array}\)¿Cual es la derivación para la cadena abbaaa?
Respuesta
¿Por qué se da la situación de existen dos tipos de lenguajes? Hasta ahora sabemos que esta es una propiedad del ecosistema de lenguajes. De la definición de los LR podemos notar que los lenguajes tienen que ver con las composicionalidad de los lenguajes, la composicionalidad permite construir un sin fin de estructuras/patrones, una analogía serían los legos que nos permiten de consturuir un sin fin de formas; mientras que los LLC tienen que ver con la estructura en particular la de un árbol, una analogía sería la construcción de un puente; es importante notar que es posible construir un puente con legos, sin embargo las GLC permiten la construcción de un infinito número de puentes con una estructura finita, situación que los LR no permiten.
Sin embargo todavía hay varías preguntas sin responder:
- ¿Cuál es la relación entre los LR y LLC?
- ¿Hay una gramática para los LR?
- ¿Hay una máquina para los LLC?