En la sección anterior identificamos al lenguaje formado por cadenas del tipo \( a^nb^n \) que no es regular ¿Entonces qué es? Antes de poder explicar más sobre este lenguaje vamos a presentar el concepto de gramáticas a través del tipo denominado libres de contexto, que nos ayudarán a generar cadenas de este lenguaje.
GLC #
- \(V\) es un alfabeto de símbolos no terminales o símbolos auxiliares
- \(\Sigma\) es un alfabeto de símbolos terminales que conforman nuestras cadenas
- \(P\) es un conjunto de reglas con la forma \(A \rightarrow \alpha\) donde \(\alpha \in \left(\Sigma \cup V \right)^*\)
- \(S \in V\) lo denominamos símbolo inicial
Algunas preferencias en la notación
- Es usual definir los símbolos no terminales con mayúsculas.
- Es usual definir los símbolos terminales con minúsculas.
- Es usual usar S, de start, o R, de root, como símbolos iniciales.
- En las reglas, a la parte izquierda de estas (antes de la flecha) se le denomina cabeza de la regla, y la parte derecha (después de la flecha) se le denomina cuerpo de la regla.
Ejemplo de GLC #
Un ejemplo de gramática es \(\left(\{S\},\{a,b\},\{S\rightarrow aSb,S\rightarrow \varepsilon\},S \right)\)
También es correcto definirla de la siguiente forma:
\(\left(\{S\},\{a,b\},P,S \right)\) donde P: \[ \begin{array}{ll} S \rightarrow & aSb\\ S \rightarrow & \varepsilon \end{array} \]
Algunas preferencias en la notación
- Es común usar una | para agrupar reglas que tienen la misma cabeza. De tal forma que la definición puede ser:
\(\left(\{S\},\{a,b\},P,S \right)\) donde P: \[ \begin{array}{ll} S \rightarrow & aSb | \varepsilon \end{array} \]
\[ \begin{array}{ll} S \rightarrow & aSb | \varepsilon \end{array} \]
- También es común omitir la tupla y sólo poner las reglas; en este caso los elementos se infieren de las reglas. De tal forma que la definición de la gramática puede ser simplemente:
Proceso de re-escritura #
Las gramáticas se interpretan con un proceso de re-escritura; uno comienza del símbolo inicial y re-escribe símbolos no terminales hasta que lo que quede sea una cadena conformada por símbolos no terminales.
Al camino seguido de re-escritura para generar una cadena se denomina derivacion; para señalar los pasos intermedios se usa el símbolo \(\Rightarrow\) .
Ejemplo de derivación #
Usando la gramática \( S \rightarrow aSb | \varepsilon \) se puede generar la siguiente derivación:
\[ \begin{array}{rll} \underline{S} &\Rightarrow & a\underline{S}b \\ & \Rightarrow & aa\underline{S}bb \\ & \Rightarrow & aaa\underline{S}bbb \\ & \Rightarrow & aaaa\underline{S}bbbb \\ & \Rightarrow & aaaaa\underline{S}bbbbb \\ & \Rightarrow & aaaaa\varepsilon bbbbb = aaaaabbbbb\\ \end{array}\]Algunas preferencias en la notación
- Es común usar el símbolo \( \Rightarrow^* \) para significar que el siguiente paso en realidad requiere múltiples pasos intermedios. Por ejemplo, la cadena anteriormente generada puede escribirse como: \[ \begin{array}{rll} \underline{S} &\Rightarrow^* & aaaaabbbbb\\ \end{array} \]
El lenguaje generado por una GLC #
Debe ser intuitivo que la gramática de ejemplo hasta este momento genera únicamente cadenas de la forma \( a^nb^n \) . En este momento tenemos un gramática que genera el lenguaje que no es regular. Como existen muchas gramáticas, hay muchos lenguajes generados por las GLC, y muchos de estos lenguajes no son Lenguajes Regulares. A los lenguajes generados por las GLC se les denomina Lenguajes Libres de Contexto.
Formalmente un lenguje L generado por una gramática G se define como \( L=\{ w | S \Rightarrow^* w \} \) donde S es el símbolo inicial de la gramática \(G=\left(V,\Sigma,P,S \right)\) . Es decir el lenguaje de asociado a una gramática es el conjunto de todas las cadenas que se derivan partiendo del símbolo inicial y siguiendo las reglas de producción.