TEMA 3 – LENGUAJES INDEPENDIENTES DEL CONTEXTO.

Gramáticas Regulares:

Los lenguajes regulares son un caso particular de los lenguajes independientes del contexto, y por ello, aparte de ser generados por autómatas finitos (AF), podrán ser generados también por gramáticas (LR –> expresiones regulares y AF; LIC –> gramáticas independientes del contexto y autómatas a pila). Una gramática regular G es una 4-tupla G=(Σ, N, S, P) donde: Σ es un alfabeto, N es una colección de símbolos NO terminales, S es un no terminal llamado símbolo inicial y P es una colección de reglas de sustitución, llamadas producciones (reglas de producción o reescritura) que son de la forma A –> w, donde A ∈ N y w ∈ (Σ ∪ N)^*. Esta gramática satisface lo siguiente: 1) w contiene un no terminal como máximo; 2) si w contiene un no terminal, entonces es el símbolo que está en el extremo derecho de w.

El lenguaje generado por la gramática regular G se denota por L(G). L(G)={w ∈ Σ^* / S =⇒ w}. «–>» se interpreta como «es sustituido por». «|» se interpreta como «o». «=>» se interpreta como «deriva», «produce» o «genera». «=⇒» indica derivar 0 o más veces. «=+>» indica derivar 1 o más veces. «=p>» indica derivar p veces.

Gramáticas Regulares (GR’s) y Lenguajes Regulares (LR’s):

Supongamos que L es un LR. Se puede obtener una GR que genere L por medio de un AF M=(Q, Σ, q₀, δ, F) para el cual L = L(M). AF –> GR: definimos G=(N, Σ, S, P) por: N = Q; Σ = Σ; S = q₀; P={ q –> a_p / (q, a) = p} ∪ { q –> ε / q ∈ F}, es decir, q –> a_p siempre que (q, a) = p y q –> ε si q es un estado de aceptación del AF. Todo LR es generado por una GR. GR –> AF: también se puede, a partir de una gramática regular G=(N, Σ, S, P), construir un AF M=(Q, Σ, s, F, δ) de forma que L(G) = L(M): Q = N ∪ {f}, donde f es un símbolo nuevo; s = S; F = {f} y δ se construye como se indica a continuación a partir de las producciones de P: 1) Si A –> … B es una producción de P con A y B como no terminales, entonces se añadirán a Q los nuevos estados q₁, q₂, …, q_{n – 1} y las transiciones siguientes: (A, a) = q₁, (q₁, b) = q₂, …, (q_n-1, ε) = B. 2) Si A –> … es una producción de P, entonces se añadirán a Q los nuevos estados q₁, q₂, …, q_{n – 1} y hacemos (A, a) = q₁, (q₁, b) = q₂, …, (q_n-1, ε) = f.

Gramáticas Independientes del Contexto (GIC’s):

Una GIC es una 4-tupla G = (N, Σ, S, P) donde N es una colección finita de no terminales, Σ es un alfabeto (conjunto de terminales), S es un no terminal (símbolo inicial) y P ⊆ N x (N ∪ Σ)^* (podemos incluir cualquier cosa por la derecha) es un conjunto de producciones. Son GIC’s porque siempre que tenga un símbolo no terminal y una producción para él, puedo ejecutarla («puedo hacer el cambio»). El lenguaje generado por la GIC G se denota por L(G) y se llama lenguaje independiente del contexto (LIC). Los LR son un subconjunto de los LIC. Todo LR está generado por una GR y toda GR es independiente del contexto, por lo tanto, todo LR es independiente del contexto.

Árboles de Derivación y Ambigüedad:

A veces es útil realizar un gráfico de la derivación que indique de qué manera ha contribuido cada no terminal a formar la cadena final de símbolos terminales. Tal gráfico se llama árbol de derivación. Un árbol para una derivación dada se construye creando un nodo raíz que se etiqueta con el símbolo inicial. El nodo raíz tiene unos nodos hijos para cada símbolo que aparezca en el lado derecho de la producción usada para reemplazar el símbolo inicial. Todo hijo etiquetado con un no terminal también tiene unos nodos hijos etiquetados con los símbolos del lado derecho de la producción usada para sustituir ese no terminal. Los nodos que no tienen hijos (nodos hoja) deben ser etiquetados con símbolos terminales.

Hay ocasiones en que, para una gramática, una derivación de una cadena puede tener árboles de derivación diferentes. Una gramática es ambigua si hay 2 o más árboles de derivación distintos para la misma cadena. Una gramática en la cual, para toda cadena w, todas las derivaciones tienen el mismo árbol de derivación, es no ambigua. En algunos casos, si la gramática es ambigua, se puede encontrar otra gramática que produzca el mismo lenguaje (equivalente) pero que no sea ambigua (no siempre es posible). Si todas las GIC’s para un lenguaje son ambiguas, se dice que el lenguaje es un LIC inherentemente ambiguo (no se puede construir una gramática no ambigua para ese lenguaje).

En una derivación por la izquierda, el no terminal que se expande es, siempre, el del extremo izquierdo. En una derivación por la derecha, el no terminal que se expande siempre es el del extremo derecho.

Simplificación de GIC’s:

Dada G=(N, Σ, P, S), la transformaremos en una G’=(N’, Σ’, P’, S) tal que L(G) = L(G’). Algoritmos de Limpieza:

A) Eliminación de No Terminales Inútiles:

1. Inicializar N’ con todos los no terminales A tales que A –> w ∈ P, con w ∈ Σ.
2. Inicializar P’ con todas las producciones A –> w para las cuales A ∈ N’ y w ∈ Σ.
3. Repetir: añadir a N’ todos los no terminales A tales que A –> w, con w ∈ (Σ ∪ N’)^* es una regla de P, y añadir también dicha regla a P hasta que no se puedan añadir más no terminales a N’ (este bucle termina siempre porque N y P son finitos).