¡Claro! Vamos a resolver paso a paso la demostración de que el conjunto \[ CFL = \{\langle M \rangle \mid L(M) \text{ es un lenguaje independiente del contexto}\} \] **no es recursivo**, **sin usar el teorema de Rice** y **reduciéndolo a un lenguaje conocido que no es recursivo**. --- ## **Paso 1: Elegir un lenguaje conocido no recursivo** Elegimos el lenguaje de la parada, que es **no recursivo**: \[ HALT = \{\langle M, w \rangle \mid \text{M es una máquina de Turing que acepta la entrada } w\} \] --- ## **Paso 2: Recordar la sugerencia** La sugerencia dice que \(\emptyset\) y \(\Sigma^*\) son lenguajes CFL. --- ## **Paso 3: Idea de la reducción** Queremos reducir el problema de decidir HALT al problema de decidir si un lenguaje es CFL. Es decir, si pudiéramos decidir CFL, podríamos decidir HALT (lo cual es imposible porque HALT no es recursivo). Por lo tanto, CFL tampoco puede ser recursivo. --- ## **Paso 4: Construcción de la reducción** ### Dado una instancia \(\langle M, w \rangle\) de HALT, construiremos una máquina de Turing \(M'\) tal que: - Si \(M\) acepta \(w\), entonces \(L(M') = \Sigma^*\) (que es CFL). - Si \(M\) no acepta \(w\), entonces \(L(M') = \emptyset\) (que es CFL). Pero esto no nos ayuda porque ambos lenguajes siempre son CFL. Necesitamos una construcción tal que: - Si \(M\) acepta \(w\), \(L(M') = \Sigma^*\) (CFL). - Si \(M\) no acepta \(w\), \(L(M')\) **no es CFL**. ### Mejor construcción: Sea \(A\) un lenguaje que **no es CFL** (por ejemplo, \(\{a^n b^n c^n \mid n \geq 0\}\)). Definimos \(M'\) de la siguiente manera: - \(M'\) en la entrada \(x\): - Simula a \(M\) en la entrada \(w\). - Si \(M\) acepta \(w\), \(M'\) acepta cualquier \(x\) (es decir, \(L(M') = \Sigma^*\)). - Si \(M\) no acepta \(w\), \(M'\) acepta \(x\) **si y solo si** \(x \in A\) (\(L(M') = A\)). Así, \[ L(M') = \begin{cases} \Sigma^* & \text{si } M \text{ acepta } w \\ A & \text{si } M \text{ no acepta } w \end{cases} \] --- ## **Paso 5: Usar el supuesto de que CFL es recursivo** Supón que existe un decidor para CFL. Dado \(\langle M, w \rangle\): 1. Construimos la máquina \(M'\) como arriba. 2. Preguntamos si \(L(M')\) es CFL. - Si responde "sí", entonces \(L(M') = \Sigma^*\) (ya que \(A\) no es CFL), por lo que \(M\) acepta \(w\). - Si responde "no", entonces \(L(M') = A\) (no es CFL), por lo que \(M\) no acepta \(w\). Así, **decidir CFL nos permite decidir HALT**, lo cual es imposible porque HALT no es recursivo. --- ## **Paso 6: Conclusión** Por lo tanto, **CFL no es recursivo**. --- ### **Respuesta final** \[ \boxed{ CFL = \{\langle M \rangle \mid L(M) \text{ es un lenguaje independiente del contexto}\} } \] **no es recursivo** porque, si lo fuera, podríamos decidir el problema de la parada mediante una reducción, y sabemos que HALT no es recursivo. ¿Te gustaría ver el pseudocódigo de la reducción?