Quiz de practica — Parcial 2

$M = (\{q_0, q_1, q_f\}, \{a, b\}, \{X, Z_0\}, \delta, q_0, Z_0, \{q_f\})$

Transiciones:

Idea: En $q_0$ se apilan $X$‘s por cada $a$. Al leer la primera $b$, se transita a $q_1$ desapilando. En $q_1$ se desapila una $X$ por cada $b$. Si la pila queda con solo $Z_0$, se acepta. Se requiere $n \geq 1$ porque no hay transicion $\delta(q_0, \varepsilon, Z_0) \to q_f$.

La cadena es aceptada porque se consume toda la entrada y se alcanza el estado final $q_f$.

$M = (\{q\}, \{a, b\}, \{S, A, B, a, b\}, \delta, q, S)$

Transiciones de produccion (reemplazar variable en tope de pila por lado derecho):

Transiciones de emparejamiento (consumir terminal si coincide con tope):

Nota: El PDA simula una derivacion por la izquierda. La pila almacena la forma sentencial restante. Se acepta cuando la pila queda vacia y la entrada se ha consumido.

(a) Verdadero. Si $G_1$ genera $L_1$ y $G_2$ genera $L_2$ (con variables disjuntas), se construye $G$ con nueva variable inicial $S \to S_1 \mid S_2$. Entonces $L(G) = L_1 \cup L_2$.

(b) Falso. Contraejemplo clasico: $L_1 = \{a^n b^n c^m \mid n, m \geq 0\}$ y $L_2 = \{a^m b^n c^n \mid n, m \geq 0\}$ son ambos LLC, pero $L_1 \cap L_2 = \{a^n b^n c^n \mid n \geq 0\}$ no es libre de contexto.

(c) Falso. Si los LLC fueran cerrados bajo complemento, por las leyes de De Morgan ($L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$) tambien serian cerrados bajo interseccion, lo cual contradice (b).

(d) Verdadero. Se demuestra con la construccion producto: dado un PDA $P$ para $L_1$ y un DFA $D$ para $L_2$, se construye un PDA que simula ambos en paralelo. El PDA resultante acepta $L_1 \cap L_2$.

(e) Verdadero. Se tiene $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$. Como $L_2$ es regular, $\overline{L_2}$ es regular (los regulares son cerrados bajo complemento). Por (d), la interseccion de un LLC con un regular es LLC.

Lema de bombeo (CFL): Si $L$ es un LLC, entonces existe $p \geq 1$ tal que toda cadena $z \in L$ con $|z| \geq p$ se puede descomponer como $z = uvwxy$ donde:

1. $|vwx| \leq p$
2. $|vx| \geq 1$
3. Para todo $i \geq 0$: $uv^iwx^iy \in L$

Demostracion por contradiccion:

Supongamos que $L$ es libre de contexto. Sea $p$ la constante del lema de bombeo. Elegimos $z = a^p b^p c^p \in L$, con $|z| = 3p \geq p$.

Por el lema, $z = uvwxy$ con $|vwx| \leq p$ y $|vx| \geq 1$.

Como $|vwx| \leq p$, la subcadena $vwx$ no puede contener simultaneamente $a$‘s y $c$‘s (estan separadas por $p$ caracteres $b$). Por lo tanto, $vx$ contiene a lo sumo dos de los tres simbolos.

Caso 1: $vx$ contiene solo $a$‘s y/o $b$‘s (no contiene $c$‘s). Entonces $uv^2wx^2y$ tiene mas $a$‘s o $b$‘s que $c$‘s, asi que $uv^2wx^2y \notin L$.

Caso 2: $vx$ contiene solo $b$‘s y/o $c$‘s (no contiene $a$‘s). Entonces $uv^2wx^2y$ tiene mas $b$‘s o $c$‘s que $a$‘s, asi que $uv^2wx^2y \notin L$.

En todos los casos, bombear con $i = 2$ produce una cadena fuera de $L$, contradiciendo el lema. Por lo tanto, $L$ no es libre de contexto. $\blacksquare$

Estrategia: Comparar el primer simbolo con el ultimo, luego el segundo con el penultimo, y asi sucesivamente.

Estados:

• $q_0$: estado inicial. Leer el primer simbolo de la cinta.
• $q_a$: se leyo una $a$ al inicio. Buscar el final para verificar que tambien sea $a$.
• $q_b$: se leyo una $b$ al inicio. Buscar el final para verificar que tambien sea $b$.
• $q_{\text{volver}}$: regresar la cabeza al inicio (al primer simbolo no marcado).
• $q_{\text{aceptar}}$: estado de aceptacion.
• $q_{\text{rechazar}}$: estado de rechazo.

Algoritmo:

1. Leer y marcar el primer simbolo. En $q_0$, leer el simbolo bajo la cabeza. Si es blanco ($\sqcup$), aceptar (cadena vacia o todos los simbolos ya fueron verificados). Si es $a$, reemplazarlo por $X$, ir a $q_a$. Si es $b$, reemplazarlo por $X$, ir a $q_b$.

2. Mover al final. En $q_a$ o $q_b$, mover la cabeza a la derecha hasta encontrar $\sqcup$ o $X$, luego retroceder una posicion para posicionarse sobre el ultimo simbolo no marcado.

3. Verificar el ultimo simbolo. Si el simbolo coincide con el primero (ej: $q_a$ y se lee $a$), marcarlo con $X$ e ir a $q_{\text{volver}}$. Si no coincide, ir a $q_{\text{rechazar}}$. Si ya esta marcado (solo quedaba un simbolo), aceptar.

4. Regresar al inicio. En $q_{\text{volver}}$, mover la cabeza a la izquierda hasta encontrar $X$, luego avanzar una posicion a la derecha y volver a $q_0$.

5. Repetir hasta aceptar o rechazar.

Complejidad: $O(n^2)$ pasos para una cadena de longitud $n$.

(a) Tipo 3 — Lenguaje regular.

Se reconoce con un DFA de dos estados que alterna entre “par” e “impar” al leer un $0$. La expresion regular es: (1*01*01*)*1*. Pertenece al nivel mas bajo de la jerarquia.

(b) Tipo 2 — Lenguaje libre de contexto (no regular).

Es generado por la gramatica $S \to aSb \mid \varepsilon$ (tipo 2). No es regular: el lema de bombeo para lenguajes regulares lo demuestra facilmente (bombeando $a^p b^p$, se desbalancea la cantidad de $a$‘s y $b$‘s).

(c) Tipo 1 — Lenguaje sensible al contexto (no libre de contexto).

Se demostro en la Pregunta 5 que no es LLC. Sin embargo, es sensible al contexto: se puede construir una gramatica sensible al contexto (o equivalentemente, un automata linealmente acotado) que lo reconozca. La gramatica usa reglas como $CB \to BC$ para reordenar simbolos.

(d) No es recursivo (fuera de la jerarquia, o Tipo 0 / RE).

Este es el problema de la detencion (Halting problem). Es recursivamente enumerable (Tipo 0): se puede construir una MT que simule la MT dada y acepte si se detiene. Pero no es decidible (no es recursivo), ya que no existe MT que siempre se detenga y decida este lenguaje (demostrado por Turing via diagonalizacion).

$M = (\{q_{\text{par}}, q_{\text{impar}}\}, \{0, 1\}, \delta, q_{\text{par}}, \{q_{\text{par}}\})$

Tabla de transiciones:

• $q_{\text{par}}$: se han leido un numero par de $0$‘s (estado inicial y de aceptacion).
• $q_{\text{impar}}$: se han leido un numero impar de $0$‘s.
• Los $1$‘s no cambian de estado (son irrelevantes para la paridad de $0$‘s).
• La cadena vacia $\varepsilon$ se acepta (cero es par).

(a) Falso. Existen lenguajes inherentemente ambiguos: todo LLC tiene al menos una gramatica, pero algunos lenguajes son tales que toda gramatica que los genere es ambigua. Un ejemplo clasico es $L = \{a^i b^j c^k \mid i = j \text{ o } j = k\}$.

(b) Verdadero (con una salvedad). Toda CFG que no genera la cadena vacia puede convertirse a CNF. Si $\varepsilon \in L(G)$, se permite la regla $S \to \varepsilon$ donde $S$ no aparece en el lado derecho de ninguna otra produccion (version extendida de CNF).

(c) Verdadero. Esa es precisamente la definicion de derivacion por la izquierda (leftmost derivation). En cada paso se expande la variable mas a la izquierda.

(d) Verdadero. Una gramatica es ambigua si y solo si existe al menos una cadena $w \in L(G)$ que tiene dos o mas arboles de derivacion distintos.

(e) Verdadero (con la misma salvedad que CNF). Todo LLC sin $\varepsilon$ tiene una gramatica en GNF, donde cada produccion tiene la forma $A \to a\alpha$ con $a \in \Sigma$ y $\alpha \in V^*$. La conversion se realiza mediante el algoritmo de Greibach (sustitucion y eliminacion de recursion izquierda).

(a) Demostracion (por doble contencion):

($L(G) \subseteq \{a^n b^n \mid n \geq 1\}$):

Toda derivacion en $G$ comienza con $S \Rightarrow aAb$. Luego, en cada paso, $A \Rightarrow aAb$ agrega una $a$ a la izquierda y una $b$ a la derecha. Al aplicar $A \Rightarrow \varepsilon$, se termina la derivacion. Si se aplica $A \to aAb$ exactamente $k$ veces ($k \geq 0$) y luego $A \to \varepsilon$, se obtiene $a^{k+1}b^{k+1}$. Como $k \geq 0$, se tiene $n = k + 1 \geq 1$. Toda cadena generada pertenece a $\{a^n b^n \mid n \geq 1\}$.

($\{a^n b^n \mid n \geq 1\} \subseteq L(G)$):

Dada $a^n b^n$ con $n \geq 1$, construimos la derivacion: aplicar $S \Rightarrow aAb$, luego $A \Rightarrow aAb$ exactamente $n - 1$ veces, y finalmente $A \Rightarrow \varepsilon$. Esto produce $a^n b^n$. Por lo tanto, $a^n b^n \in L(G)$ para todo $n \geq 1$.

Se concluye que $L(G) = \{a^n b^n \mid n \geq 1\}$. $\blacksquare$

(b) Derivaciones por la izquierda:

Para $ab$ ($n = 1$):

$S \Rightarrow aAb \Rightarrow ab$

Para $aabb$ ($n = 2$):

$S \Rightarrow aAb \Rightarrow aaAbb \Rightarrow aabb$

Para $aaabbb$ ($n = 3$):

$S \Rightarrow aAb \Rightarrow aaAbb \Rightarrow aaaAbbb \Rightarrow aaabbb$