Unidad 5 Gramáticas Libres de Contexto (GLC).

Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X → α, donde X es una variable y α es una cadena que puede contener variables y constantes. Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”)

• Capturan la noción de constituyente sintáctico y la noción de orden.
• Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurador.
• Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.

Una Gramática Libre de Contexto es una tupla con 4 parámetros:

• G = (V, T, P, S)
• V – conjunto de símbolos variables
• T – conjunto de símbolos terminales
• S Є V, símbolo inicial
• P – conjunto de reglas de producción: A → α, con α sucesión de símbolos de V U T, eventualmente vacía (α = ε)

Una GLC es un dispositivo generador.

Definimos el lenguaje LG generado por una gramática G del siguiente modo: G = { w / S →* w } , siendo ⇒* una “especie” de clausura transitiva de → y w una tira de terminales

Vamos a ver los CFG’s, los lenguajes que generan, los arboles de parseo, el ´ pushdown automata y las propiedades de cerradura de los CFL’s

Ejemplo: Considere Lpal = {w ∈ Σ ∗ : w = w R}. Por ejemplo, oso ∈ Lpal, anitalavalatina ∈ Lpal,

Sea Σ = {0, 1} y supongamos que Lpal es regular.

Sea n dada por el pumping lemma. Entonces 0 n10n ∈ Lpal. Al leer 0n el FA debe de entrar a un ciclo. Si quitamos el ciclo entonces llegamos a una contradiccion.