En la sección anterior identificamos al lenguaje formado por cadenas del tipo \( a^nb^nc^n \) que no es libre de contexto ¿Entonces qué es? Antes de poder explicar más sobre este lenguaje vamos a presentar el concepto de gramáticas dependientes 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 que con la forma \(\gamma A \beta \rightarrow \gamma \alpha \beta\) donde \(\alpha \in \left(\Sigma \cup V \right)^*, \gamma \in \left(\Sigma \cup V \right)^*, \beta \in \left(\Sigma \cup V \right)^*,\)
- \(S \in V\) lo denominamos símbolo inicial
Ejemplo de GDC #
Un ejemplo de Gramática Dependiente del Contexto es:
\(\left(\{S\},\{a,b\},P,S \right)\) donde P: \[ \begin{array}{lclclcl} & S & & \rightarrow & & abC &\\ & S & & \rightarrow & & aSBC &\\ & C & B & \rightarrow & & W & B\\ W & B & & \rightarrow & W & X & \\ & W & X & \rightarrow & & B & X\\ B & X & & \rightarrow & B & C & \\ b & B & & \rightarrow & b & b & \\ b & C & & \rightarrow & b & c & \\ c & C & & \rightarrow & c & c & \\ \end{array} \]
Derivación #
De forma similar que las GLC las GDC siguen un proceso de re-escritura, a un camino de escritura de forma similar se le denomina derivación. A continuación un ejemplo de derivación para la cadena \(a^nb^nc^n\) .
\[ \begin{array}{rl} \underline{S} \Rightarrow & a\underline{S}BC\\ \Rightarrow & aa\underline{S}BCBC\\ \Rightarrow & aaab\underline{CB}CBC\\ \Rightarrow & aaab\underline{WB}CBC\\ \Rightarrow & aaab\underline{WX}CBC\\ \Rightarrow & aaab\underline{BX}CBC\\ \Rightarrow & aaabBC\underline{CB}C\\ \Rightarrow & aaabBC\underline{WB}C\\ \Rightarrow & aaabBC\underline{WX}C\\ \Rightarrow & aaabBC\underline{BX}C\\ \Rightarrow & aaabB\underline{CB}CC\\ \Rightarrow & aaabB\underline{WB}CC\\ \Rightarrow & aaabB\underline{WX}CC\\ \Rightarrow & aaab\underline{BB}CCC\\ \Rightarrow & aaabb\underline{BC}CC\\ \Rightarrow & aaabb\underline{bC}CC\\ \Rightarrow & aaabbb\underline{cC}C\\ \Rightarrow & aaabbbc\underline{cC}\\ \Rightarrow & aaabbbccc\\ \end{array}\]Lenguajes Dependientes del Contexto #
Formalmente un lenguje L generado por una gramática dependiente del contexto 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 GDC es el conjunto de todas las cadenas que tienen una derivación partiendo del símbolo inicial de la gramática y a través de aplicar una secuencia finita de re-escrituras siguiendo las reglas de producción.
Algunas observaciones #
Al final de esta sección podemos concentrar lo que sabemos en la siguiente tabla:
| Lenguaje | Gramática | Máquina | Ejemplo |
|---|---|---|---|
| Lenguaje Dependientes del Contexto | \( \gamma A \beta \rightarrow \gamma \alpha \beta \) | ?? | \( a^nb^nc^n \) |
| Lenguaje Independiente del Contexto | \( A \rightarrow \alpha \) | Autómata de Pila | \( a^nb^n \) |
| Lenguaje Regular | \( A \rightarrow bC | d \) | AF, AFND y AFND-ε | \( a^n \) |
Ahora podemos ver porque se denomina a los Lenguajes Independientes del Contexto, como independientes, ya que a diferencia de los dependientes el contexto no está definido (γ y ꞵ), o mejor dicho es contexto muy particular donde gamma es epsilon y beta también.
También es importante notar, que hasta este momento si nos fijamos en la tabla los niveles de esta están definidos por la forma de las reglas. La forma de las reglas se vuelven más específicas para los niveles más abajo. Dependientes del contexto define cualquier contexto, independientes del contexto define un sólo contexto, y regulares requiere una forma peculiar de alfa.