Definición formal — CFG

Gramática libre de contexto (CFG) — 4-tupla:

$G = (V, \Sigma, P, S)$

donde:

• $V$ — conjunto finito de variables (no terminales)
• $\Sigma$ — conjunto finito de terminales ($V \cap \Sigma = \emptyset$)
• $P \subseteq V \times (V \cup \Sigma)^*$ — conjunto finito de producciones ($A \to \alpha$, con $A \in V$)
• $S \in V$ — símbolo inicial (o axioma)

Restricción clave: el lado izquierdo de toda producción es una sola variable. Esto es lo que la hace “libre de contexto” — se puede reescribir $A$ sin importar qué la rodea.

Derivación: $\alpha \Rightarrow \beta$ si $\beta$ se obtiene reemplazando un no terminal de $\alpha$ por el cuerpo de alguna producción.

• Derivación por la izquierda ($\Rightarrow_{lm}$): siempre se expande el no terminal más a la izquierda.
• Derivación por la derecha ($\Rightarrow_{rm}$): siempre se expande el no terminal más a la derecha.
• $L(G) = \{w \in \Sigma^* \mid S \Rightarrow^* w\}$

Árbol de derivación (parse tree): representación gráfica donde la raíz es $S$, los nodos internos son variables, las hojas son terminales o $\varepsilon$, y los hijos de cada nodo corresponden al cuerpo de la producción aplicada. La cosecha (yield) del árbol es la cadena que se lee de izquierda a derecha en las hojas.

Ambigüedad: Una gramática $G$ es ambigua si existe alguna cadena $w \in L(G)$ que tiene dos o más árboles de derivación distintos (equivalentemente, dos derivaciones por la izquierda distintas). Un lenguaje es inherentemente ambiguo si TODA gramática que lo genera es ambigua.

V/F importantes sobre CFG (preguntados en examen)

• Una CFG puede tener un conjunto de producciones infinito? Falso — $P$ es finito por definición.
• Una CFG con producciones $\varepsilon$ genera necesariamente $\varepsilon$? No necesariamente — depende de si $S \Rightarrow^* \varepsilon$.
• Si $G$ es ambigua, se puede siempre encontrar una gramática no ambigua equivalente? No — existen lenguajes inherentemente ambiguos.

Definición CNF

Una CFG está en Forma Normal de Chomsky si toda producción tiene una de estas dos formas:

$A \to BC \quad \text{o} \quad A \to a$

donde $A, B, C \in V$ (variables) y $a \in \Sigma$ (terminal). Adicionalmente, si $\varepsilon \in L(G)$, se permite $S \to \varepsilon$ y $S$ no aparece en el lado derecho de ninguna producción.

Los 4 pasos de conversión a CNF

Paso 1 — Eliminar producciones $\varepsilon$:

• Encontrar todas las variables anulables: $A$ es anulable si $A \Rightarrow^* \varepsilon$.
• Para cada producción que contiene una variable anulable, agregar versiones donde esa variable se omite. Ej: si $B$ es anulable y hay $A \to aBb$, agregar $A \to ab$.
• Eliminar todas las producciones $A \to \varepsilon$ (excepto $S \to \varepsilon$ si $\varepsilon \in L$).

Paso 2 — Eliminar producciones unitarias ($A \to B$):

• Encontrar todos los pares unitarios: si $A \Rightarrow^* B$ usando solo producciones unitarias.
• Por cada par $(A, B)$ y cada producción no unitaria $B \to \alpha$, agregar $A \to \alpha$.
• Eliminar todas las producciones unitarias.

Paso 3 — Reemplazar terminales en cuerpos mixtos:

• Si una producción tiene terminales mezclados con variables o longitud $\geq 2$ (ej: $A \to aBc$), reemplazar cada terminal $a$ por una nueva variable $C_a$ y agregar $C_a \to a$.

Paso 4 — Binarizar producciones largas:

• Si $A \to B_1 B_2 \cdots B_k$ con $k \geq 3$, descomponer con variables auxiliares:

$A \to B_1 D_1, \quad D_1 \to B_2 D_2, \quad \ldots, \quad D_{k-2} \to B_{k-1} B_k$

Mnemónico: “ε, unitarias, terminales, binarizar” = EUTB.

Teorema de pasos de derivación en CNF

Teorema: En una gramática en CNF, derivar una cadena $w$ con $|w| = n$ requiere exactamente $2n - 1$ pasos de derivación:

• $n - 1$ aplicaciones de reglas $A \to BC$ (cada una aumenta el número de símbolos en 1, empezando de 1 hasta llegar a $n$)
• $n$ aplicaciones de reglas $A \to a$ (una por cada terminal de la cadena)

Caso particular para longitud par: Si $|w| = 2k$, se necesitan $2(2k) - 1 = 4k - 1$ pasos.

Ojo examen: Piden demostrar esto. La prueba es por inducción sobre $n$:

• Base ($n = 1$): $S \to a$, es un solo paso $= 2(1) - 1 = 1$. ✓
• Paso inductivo: Si $S \Rightarrow BC$, entonces $B \Rightarrow^* w_1$ con $|w_1| = k$ y $C \Rightarrow^* w_2$ con $|w_2| = n - k$. Por HI, $B$ usa $2k - 1$ pasos y $C$ usa $2(n-k) - 1$ pasos. Total: $1 + (2k-1) + (2(n-k)-1) = 2n - 1$. ✓

V/F sobre CNF (preguntado directamente)

• “Si $G$ está en CNF y $L(G)$ contiene cadenas de longitud impar, entonces tiene al menos una producción $A \to a$.” Verdadero — sin producciones $A \to a$, solo se generan no terminales (por $A \to BC$), nunca se llega a terminales.
• En CNF, toda cadena (par o impar) necesita producciones $A \to a$ — de lo contrario no se generan terminales.

Patrón 1: Lenguajes con $|w|_a = |w|_b$ (igual cantidad de a’s y b’s)

Gramática clásica:

$S \to aSb \mid bSa \mid SS \mid \varepsilon$

Prueba de que $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$ — por inducción sobre $|w|$:

• Base: $|w| = 0 \Rightarrow w = \varepsilon$, y $S \Rightarrow \varepsilon$. ✓
• Paso inductivo: Sea $|w| = n > 0$ con $|w|_a = |w|_b$.
  • Si $w = aw'b$ con $|w'|_a = |w'|_b$: por HI $S \Rightarrow^* w'$, entonces $S \Rightarrow aSb \Rightarrow^* aw'b = w$. ✓
  • Si $w = bw'a$: análogo con $S \to bSa$.
  • Si $w = w_1 w_2$ donde ambos tienen a’s = b’s: $S \Rightarrow SS \Rightarrow^* w_1 w_2$. ✓

Tip examen: Cuando piden “demostrar que $G$ genera $L$”, probar ambas direcciones: $L(G) \subseteq L$ (toda cadena derivable cumple la propiedad) y $L \subseteq L(G)$ (toda cadena que cumple la propiedad es derivable).

Patrón 2: Lenguajes con condiciones tipo $n \geq m$ o $n \leq 2m$

Estrategia: generar la parte balanceada primero, luego el exceso.

Ejemplo — $L = \{a^n b^m \mid n \geq m \geq 0\}$:

$S \to aS \mid aSb \mid \varepsilon$

Idea: cada $b$ se “aparea” con una $a$ (regla $aSb$), las $a$‘s extras se generan por $aS$.

Ejemplo — $L = \{a^n b^m \mid n \leq 2m\}$:

$S \to aSb \mid aaSb \mid Sb \mid \varepsilon$

Cada $b$ puede “absorber” 0, 1 o 2 $a$‘s.

Patrón 3: Uniones de lenguajes

Si $L = L_1 \cup L_2$, simplemente:

$S \to S_1 \mid S_2$

donde $S_1$ genera $L_1$ y $S_2$ genera $L_2$. Funciona porque CFL es cerrado bajo unión.

Patrón 4: Regex $\to$ CFG con tabla de derivaciones

Conversión sistemática:

• Concatenación $r_1 r_2$: $A \to A_1 A_2$
• Unión $r_1 \mid r_2$: $A \to A_1 \mid A_2$
• Estrella $r^*$: $A \to A_1 A \mid \varepsilon$
• Positiva $r^+$: $A \to A_1 A \mid A_1$ (o equivalente $A \to A_1 B$, $B \to A_1 B \mid \varepsilon$)
• Símbolo $a$: $A \to a$

Después de convertir, hacer tabla de derivaciones para al menos 3 cadenas del lenguaje mostrando paso a paso cada derivación.

Patrón 5: Familias de gramáticas $G_n$

Examen define familias como $G_n = (V_n, \Sigma, P_n, S)$ parametrizadas por $n$ y piden probar propiedades (ej: “toda cadena generada tiene longitud par”).

Estrategia: inducción sobre la longitud de la derivación o sobre $n$. Verificar con casos pequeños ($G_1$, $G_2$) para entender el patrón antes de generalizar.

Definición formal — PDA

Autómata de Pila (PDA) — 7-tupla:

$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$

donde:

• $Q$ — conjunto finito de estados
• $\Sigma$ — alfabeto de entrada
• $\Gamma$ — alfabeto de pila
• $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$ — función de transición
• $q_0 \in Q$ — estado inicial
• $Z_0 \in \Gamma$ — símbolo inicial de la pila
• $F \subseteq Q$ — estados de aceptación

Transición: $\delta(q, a, X) = \{(p, \gamma), \ldots\}$ — estando en estado $q$, leyendo $a$ del input y $X$ del tope de la pila, paso al estado $p$ y reemplazo $X$ por $\gamma$ en la pila. Si $\gamma = \varepsilon$, hago pop. Si $a = \varepsilon$, no consumo input (transición espontánea).

Descripción instantánea (ID): $(q, w, \gamma)$ — estado actual, input restante, contenido de la pila (tope a la izquierda).

• $\vdash$ = un paso de computación
• $\vdash^*$ = cero o más pasos

Dos modos de aceptación:

• Por estado final: $w \in L(M)$ si $(q_0, w, Z_0) \vdash^* (q_f, \varepsilon, \alpha)$ con $q_f \in F$
• Por pila vacía: $w \in N(M)$ si $(q_0, w, Z_0) \vdash^* (q, \varepsilon, \varepsilon)$
• Ambos modos son equivalentes en poder — se pueden convertir entre sí

DPDA vs NPDA: A diferencia de DFA/NFA, un DPDA es estrictamente menos poderoso que un NPDA. Ejemplo: $\{ww^R \mid w \in \{0,1\}^*\}$ necesita no determinismo (hay que “adivinar” el medio).

V/F sobre PDA (preguntado en examen)

• “Un PDA puede aceptar $\{\varepsilon\}$?” Sí — por pila vacía: hacer pop de $Z_0$ inmediatamente ($\delta(q_0, \varepsilon, Z_0) = \{(q_0, \varepsilon)\}$). Por estado final: poner $q_0 \in F$.
• “Todo DPDA puede convertirse en NPDA equivalente?” Sí — todo DPDA es un caso particular de NPDA.
• “Todo NPDA puede convertirse en DPDA equivalente?” No — NPDA es estrictamente más poderoso.

Teorema de equivalencia

Todo lenguaje libre de contexto tiene un PDA que lo reconoce, y viceversa. Tres construcciones:

1. CFG $\to$ PDA de estado único (LA CONSTRUCCIÓN MÁS PREGUNTADA)

Dada $G = (V, \Sigma, P, S)$, construir $M = (\{q\}, \Sigma, V \cup \Sigma, \delta, q, S, \emptyset)$:

• Un solo estado $q$
• Aceptación por pila vacía (sin estados finales)
• Para cada producción $A \to \alpha \in P$: $\delta(q, \varepsilon, A) \ni (q, \alpha)$
• Para cada terminal $a \in \Sigma$: $\delta(q, a, a) \ni (q, \varepsilon)$

Intuición: El PDA simula una derivación por la izquierda. La pila contiene la forma sentencial pendiente. Los no terminales se expanden (transiciones $\varepsilon$), los terminales se emparejan con el input (se consumen).

Ejemplo rápido: Para $S \to aSb \mid \varepsilon$:

• $\delta(q, \varepsilon, S) = \{(q, aSb), (q, \varepsilon)\}$
• $\delta(q, a, a) = \{(q, \varepsilon)\}$
• $\delta(q, b, b) = \{(q, \varepsilon)\}$

2. PDA $\to$ CFG

Variables de la forma $[q_i A q_j]$ que representan “ir de $q_i$ a $q_j$ vaciando $A$ de la pila”.

Si $\delta(q_i, a, A) \ni (q_k, B_1 B_2 \cdots B_m)$, generar producciones:

$[q_i A q_j] \to a\,[q_k B_1 q_{r_1}]\,[q_{r_1} B_2 q_{r_2}] \cdots [q_{r_{m-1}} B_m q_j]$

para toda combinación de estados intermedios.

3. Demostrar $L(M) = L(G)$ (patrón de examen)

Usar el lema de correspondencia: hay una biyección entre derivaciones por la izquierda de $G$ y secuencias de configuraciones de $M$.

Demostrar: $S \Rightarrow_{lm}^* w$ $\iff$ $(q, w, S) \vdash^* (q, \varepsilon, \varepsilon)$

Ambas direcciones por inducción sobre el número de pasos.

Patrón: Diseñar NPDA para $L$

Siempre dar:

1. La 7-tupla completa
2. Todas las transiciones (tabla o diagrama)
3. Traza de al menos 2 cadenas de ejemplo

Ejemplo: $L = \{a^n b^m c^k \mid k = |n - m|\}$

Idea: la pila cuenta la diferencia entre $n$ y $m$.

• Fase 1: leer $a$‘s, apilar una marca por cada $a$
• Fase 2: leer $b$‘s, desapilar por cada $b$
  • Si la pila se vacía antes de acabar las $b$‘s, apilar las $b$‘s restantes con marca distinta
• Fase 3: leer $c$‘s, desapilar una marca por cada $c$
• Aceptar cuando input y pila están vacíos

Ejemplo: $L = \{a^n b^m \mid m = 3n\}$

Idea: por cada $a$, empujar 3 marcas; por cada $b$, sacar 1 marca.

$\delta(q_0, a, Z_0) = \{(q_0, AAAZ_0)\}$ $\delta(q_0, a, A) = \{(q_0, AAAA)\}$ $\delta(q_0, \varepsilon, A) = \{(q_1, A)\} \quad \text{(transición a fase de b's)}$ $\delta(q_1, b, A) = \{(q_1, \varepsilon)\}$ $\delta(q_1, \varepsilon, Z_0) = \{(q_f, \varepsilon)\} \quad \text{(aceptar)}$

Tip: Para relaciones tipo $m = kn$, empujar $k$ símbolos por cada lectura de una letra y sacar 1 por cada lectura de la otra.

Ejemplo: CFG $\to$ NPDA de estado único (conversión directa)

Dado una CFG del examen, mecánicamente construir el PDA:

1. Un estado $q$
2. Alfabeto de pila = $V \cup \Sigma$
3. Para cada producción $A \to \alpha$: transición $\varepsilon$ que reemplaza $A$ por $\alpha$
4. Para cada terminal: transición que empareja y hace pop
5. Aceptación por pila vacía

Luego trazar la aceptación de una cadena mostrando cada ID.

Propiedades de clausura

Cerrados bajo:

• Unión: Si $L_1, L_2$ son CFL, entonces $L_1 \cup L_2$ es CFL. ($S \to S_1 \mid S_2$)
• Concatenación: $L_1 \cdot L_2$ es CFL. ($S \to S_1 S_2$)
• Estrella de Kleene: $L^*$ es CFL. ($S \to SS_1 \mid \varepsilon$)
• Intersección con regular: Si $L$ es CFL y $R$ es regular, $L \cap R$ es CFL. (Producto de PDA con DFA)

NO cerrados bajo:

• Intersección entre CFLs — contraejemplo: $L_1 = \{a^n b^n c^m\}$ y $L_2 = \{a^m b^n c^n\}$ son CFL, pero $L_1 \cap L_2 = \{a^n b^n c^n\}$ no es CFL.
• Complemento — si fuera cerrado bajo complemento, por De Morgan sería cerrado bajo intersección. Contradicción.

Lema de Bombeo para CFL

Enunciado: Si $L$ es un CFL, existe $p > 0$ tal que toda $w \in L$ con $|w| \geq p$ se puede descomponer como:

$w = uvxyz$

con:

1. $|vxy| \leq p$
2. $|vy| > 0$ (al menos uno de $v, y$ es no vacío)
3. $uv^ixy^iz \in L$ para todo $i \geq 0$

Diferencia con lema regular: Acá hay dos piezas bombeables ($v$ e $y$) que crecen juntas. Vienen de un no terminal que se repite en el árbol de derivación.

Estrategia para probar $L$ no es CFL:

1. Asumir que $L$ es CFL, sea $p$ la longitud de bombeo
2. Elegir $w \in L$ con $|w| \geq p$ (elegir inteligentemente!)
3. Para toda descomposición $w = uvxyz$ con $|vxy| \leq p$ y $|vy| > 0$…
4. Mostrar un $i$ tal que $uv^ixy^iz \notin L$

Ejemplo clásico: $L = \{a^n b^n c^n \mid n \geq 0\}$ no es CFL.

• Elegir $w = a^p b^p c^p$
• Como $|vxy| \leq p$, la ventana $vxy$ toca a lo sumo 2 de los 3 símbolos
• Bombear ($i = 2$): los conteos se desequilibran porque no podemos aumentar los 3 simultáneamente

Truco rápido: Si necesitas probar que algo no es CFL, intenta intersectarlo con un regular para obtener $\{a^n b^n c^n\}$ o similar.

Definición — Máquina de Turing

Máquina de Turing (MT) — 7-tupla:

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

donde:

• $Q$ — conjunto finito de estados
• $\Sigma$ — alfabeto de entrada ($B \notin \Sigma$, donde $B$ es el blanco)
• $\Gamma$ — alfabeto de cinta ($\Sigma \subseteq \Gamma$, $B \in \Gamma$)
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ — función de transición
• $q_0$ — estado inicial
• $q_{accept}$ — estado de aceptación
• $q_{reject}$ — estado de rechazo ($q_{accept} \neq q_{reject}$)

Decidible (recursivo): Existe MT que siempre se detiene — acepta o rechaza.

Turing-reconocible (r.e.): Existe MT que acepta las cadenas de $L$. Para $w \notin L$, puede rechazar o loopear.

$L$ y $\overline{L}$ ambos Turing-reconocibles $\Rightarrow$ $L$ es decidible.

Jerarquía de Chomsky completa

$\text{Regular} \subsetneq \text{CFL} \subsetneq \text{CSL} \subsetneq \text{RE} \subsetneq \text{Todos}$

Tesis de Church-Turing

Todo procedimiento efectivo (algoritmo intuitivo) puede ser simulado por una Máquina de Turing. No es un teorema formal — es una tesis que formaliza “computable”. Toda evidencia la respalda: MT, cálculo lambda, funciones recursivas computan lo mismo.

Tuplas

• CFG: $G = (V, \Sigma, P, S)$ — variables, terminales, producciones, símbolo inicial
• PDA: $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ — estados, input, pila, transición, inicio, fondo pila, finales
• MT: $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

CNF

• Solo $A \to BC$ y $A \to a$
• Pasos conversión: ε → unitarias → terminales → binarizar
• Derivar $|w| = n$: exactamente $2n - 1$ pasos ($n-1$ reglas $A \to BC$ + $n$ reglas $A \to a$)
• Para $|w| = 2k$: $4k - 1$ pasos

CFG $\to$ PDA (un solo estado)

• Un estado $q$, aceptación por pila vacía
• Producciones = transiciones $\varepsilon$: $\delta(q, \varepsilon, A) \ni (q, \alpha)$
• Terminales = emparejar: $\delta(q, a, a) \ni (q, \varepsilon)$

Clausura CFL

Lema de bombeo CFL

$w = uvxyz$, $|vxy| \leq p$, $|vy| > 0$, $uv^ixy^iz \in L$ $\forall i \geq 0$

Dos piezas bombeables (vs una en regular). Ventana $vxy$ acotada por $p$.

Checklist de diseño PDA

1. Definir la 7-tupla completa
2. Listar TODAS las transiciones
3. Trazar mínimo 2 cadenas
4. Verificar cadenas fuera del lenguaje son rechazadas

Checklist de prueba CFG genera $L$

1. $L(G) \subseteq L$: toda derivación produce cadena válida (inducción sobre pasos)
2. $L \subseteq L(G)$: toda cadena válida es derivable (inducción sobre longitud)