Edición de «Demostraciones (Teoría de Lenguajes)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 633: | Línea 633: | ||
** El caso base es long=1, con lo cual la única transición posible <math>\lambda</math> (por '''1''') y <math>\gamma</math> tiene que ser la cadena vacía. Como <math>\delta(q_0,\gamma) = \delta(q_0,\lambda)</math> y <math>S \rightarrow . \alpha \in \delta(q_0,\lambda)</math> y es además un item válido para el prefijo viable <math>\gamma = \lambda</math>, el caso base se cumple. | ** El caso base es long=1, con lo cual la única transición posible <math>\lambda</math> (por '''1''') y <math>\gamma</math> tiene que ser la cadena vacía. Como <math>\delta(q_0,\gamma) = \delta(q_0,\lambda)</math> y <math>S \rightarrow . \alpha \in \delta(q_0,\lambda)</math> y es además un item válido para el prefijo viable <math>\gamma = \lambda</math>, el caso base se cumple. | ||
** Para el paso inductivo asumimos verdadera la HI para long de camino menores a <math>k</math>. Las reglas para las transiciones 2) y 3) implican dos formas posibles para la última transición en el camino. Nuestra hipótesis es <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math> en <math>k</math> transiciones: | ** Para el paso inductivo asumimos verdadera la HI para long de camino menores a <math>k</math>. Las reglas para las transiciones 2) y 3) implican dos formas posibles para la última transición en el camino. Nuestra hipótesis es <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math> en <math>k</math> transiciones: | ||
**# Está etiquetada con <math>X \in V</math>: Por hipótesis y como además sabemos que en la última transición consumimos <math>X</math>, si tomamos <math>\alpha = \alpha' X</math> y <math>\gamma = \gamma' X</math>, el estado anterior tienen que ser <math>[A \rightarrow \alpha'.X \beta]</math>, al que se llegó de <math>q_0</math> por <math>\gamma'</math> en <math>k-1</math> pasos, es decir, <math>[A \rightarrow \alpha' . X \beta] \in \delta(q_0,\gamma')</math>. Pero al ser <math>k-1</math> transiciones, vale la hipótesis inductiva, o sea, vale que <math>[A \rightarrow \alpha' . X \beta]</math> es un item válido para el prefijo viable <math>\gamma'</math>. Qué significa esto? Que <math>\alpha' X \beta</math> es un pivote, también que <math>\gamma' = \delta \alpha'</math> y que <math>S \rightarrow_{D}^* \ \delta A w \ \rightarrow_{D} \ \delta \alpha' X \beta w</math> (todo por la definición de prefijo viable e item válido para el mismo). Pero entonces notemos que <math>\delta \alpha' X = \gamma</math> también cumple la definición de prefijo viable (por quién es el pivote) y que <math>[A \rightarrow \alpha' X. \beta]</math> es un item válido para <math>\gamma</math>. Como <math>[A \rightarrow \alpha' X. \beta] = [A \rightarrow \alpha . \beta]</math>, llegamos a lo que queríamos: <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math> implica <math>[A \rightarrow \alpha . \beta]</math> es un item válido para <math>\gamma</math> prefijo | **# Está etiquetada con <math>X \in V</math>: Por hipótesis y como además sabemos que en la última transición consumimos <math>X</math>, si tomamos <math>\alpha = \alpha' X</math> y <math>\gamma = \gamma' X</math>, el estado anterior tienen que ser <math>[A \rightarrow \alpha'.X \beta]</math>, al que se llegó de <math>q_0</math> por <math>\gamma'</math> en <math>k-1</math> pasos, es decir, <math>[A \rightarrow \alpha' . X \beta] \in \delta(q_0,\gamma')</math>. Pero al ser <math>k-1</math> transiciones, vale la hipótesis inductiva, o sea, vale que <math>[A \rightarrow \alpha' . X \beta]</math> es un item válido para el prefijo viable <math>\gamma'</math>. Qué significa que esto? Que <math>\alpha' X \beta</math> es un pivote, también que <math>\gamma' = \delta \alpha'</math> y que <math>S \rightarrow_{D}^* \ \delta A w \ \rightarrow_{D} \ \delta \alpha' X \beta w</math> (todo por la definición de prefijo viable e item válido para el mismo). Pero entonces notemos que <math>\delta \alpha' X = \gamma</math> también cumple la definición de prefijo viable (por quién es el pivote) y que <math>[A \rightarrow \alpha' X. \beta]</math> es un item válido para <math>\gamma</math>. Como <math>[A \rightarrow \alpha' X. \beta] = [A \rightarrow \alpha . \beta]</math>, llegamos a lo que queríamos: <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math> implica <math>[A \rightarrow \alpha . \beta]</math> es un item válido para <math>\gamma</math> prefijo válido. | ||
**# Está etiquetada con <math>\lambda</math>: Como la última transición fue <math>\lambda</math> tiene que haber sido usando la definición '''2''' de <math>\delta</math>. Primero, esto implica que para que el item tenga la forma <math>[B \rightarrow . \gamma]</math> debe pasar que <math>\alpha = \lambda</math>. Segundo, el estado previo tiene que haber sido de la forma <math>[B \rightarrow \alpha_1 . A \beta_1]</math>, y a él se tiene que haber llegado del estado inicial por el mismo <math>\gamma</math> (ya que no se consumió entrada), o sea, tiene que pertenecer a <math>\delta(q_0,\gamma)</math>. Nuevamente vale la hipótesis inductiva, entonces podemos deducir que <math>[B \rightarrow \alpha_1 . A \beta_1]</math> es item válido del prefijo viable <math>\gamma</math>. O sea, <math>S \rightarrow_{D}^* \ \delta B w \ \rightarrow_{D} \ \delta \alpha_1 A \beta_1 w \ \rightarrow_{D} \ \delta \alpha_1 \beta \beta_1 w </math> (el último paso por hipótesis y porque concluimos que <math>\alpha = \lambda</math>). Pero entonces <math>\gamma = \delta\alpha_1</math> es también prefijo viable para el pivote <math>\beta</math>, para el cual <math>[A \rightarrow \ .\beta]</math> es un item válido, llegando así a lo que queríamos probar. | **# Está etiquetada con <math>\lambda</math>: Como la última transición fue <math>\lambda</math> tiene que haber sido usando la definición '''2''' de <math>\delta</math>. Primero, esto implica que para que el item tenga la forma <math>[B \rightarrow . \gamma]</math> debe pasar que <math>\alpha = \lambda</math>. Segundo, el estado previo tiene que haber sido de la forma <math>[B \rightarrow \alpha_1 . A \beta_1]</math>, y a él se tiene que haber llegado del estado inicial por el mismo <math>\gamma</math> (ya que no se consumió entrada), o sea, tiene que pertenecer a <math>\delta(q_0,\gamma)</math>. Nuevamente vale la hipótesis inductiva, entonces podemos deducir que <math>[B \rightarrow \alpha_1 . A \beta_1]</math> es item válido del prefijo viable <math>\gamma</math>. O sea, <math>S \rightarrow_{D}^* \ \delta B w \ \rightarrow_{D} \ \delta \alpha_1 A \beta_1 w \ \rightarrow_{D} \ \delta \alpha_1 \beta \beta_1 w </math> (el último paso por hipótesis y porque concluimos que <math>\alpha = \lambda</math>). Pero entonces <math>\gamma = \delta\alpha_1</math> es también prefijo viable para el pivote <math>\beta</math>, para el cual <math>[A \rightarrow \ .\beta]</math> es un item válido, llegando así a lo que queríamos probar. | ||
* '''Vuelta (<=)''' | * '''Vuelta (<=)''' | ||
Línea 640: | Línea 640: | ||
*** Paso inductivo: (supongamos HI cierta para <math>i</math>). Por hipotesis del lemma y def. de p.v. e i.v., <math>S \rightarrow_{D}^{i+1} \ \gamma A w \ \rightarrow_{D} \ \gamma \alpha w</math> . Como el <math>A</math> tiene que haber surgido en alguna derivación anterior o igual a <math>i+1</math>, <math>S \rightarrow_{D}^k \ \gamma' B w'\rightarrow_{D} \ \gamma' \gamma'' A w'' w' \ \rightarrow_{D}^{i-k} \ \gamma A w</math> . Notar que <math>\gamma' \gamma'' = \gamma</math> ya que ningún no terminal a la derecha de <math>A</math> puede expandirse antes que esta (por ser derivación más a la derecha). Ahora, como <math>\gamma' \gamma'' A w'' w'</math> es una f.s.d, <math>[B \rightarrow .\gamma'' A w'']</math> es un ítem válido para el prefijo viable <math>\gamma'</math>. Por H.I., entonces <math>[B \rightarrow .\gamma'' A w''] \in \delta(q_0, \gamma')</math>. Pero aplicando la definición (3) de <math>\delta</math> por cada símbolo de <math>\gamma'</math> se ve que podemos llegar del estado <math>[B \rightarrow .\gamma'' A w'']</math> a <math>[B \rightarrow \gamma'' . A w'']</math> consumiendo <math>\gamma''</math>. Entonces, <math>[B \rightarrow \gamma'' . A w''] \in \delta(q_0, \gamma' \gamma'') = \delta(q_0, \gamma)</math> . Para terminar, por la def. (2), <math>[A \rightarrow .\alpha] \in \delta(\delta(q_0, \gamma), \lambda) = \delta(q_0, \gamma)</math>, como queríamos probar. | *** Paso inductivo: (supongamos HI cierta para <math>i</math>). Por hipotesis del lemma y def. de p.v. e i.v., <math>S \rightarrow_{D}^{i+1} \ \gamma A w \ \rightarrow_{D} \ \gamma \alpha w</math> . Como el <math>A</math> tiene que haber surgido en alguna derivación anterior o igual a <math>i+1</math>, <math>S \rightarrow_{D}^k \ \gamma' B w'\rightarrow_{D} \ \gamma' \gamma'' A w'' w' \ \rightarrow_{D}^{i-k} \ \gamma A w</math> . Notar que <math>\gamma' \gamma'' = \gamma</math> ya que ningún no terminal a la derecha de <math>A</math> puede expandirse antes que esta (por ser derivación más a la derecha). Ahora, como <math>\gamma' \gamma'' A w'' w'</math> es una f.s.d, <math>[B \rightarrow .\gamma'' A w'']</math> es un ítem válido para el prefijo viable <math>\gamma'</math>. Por H.I., entonces <math>[B \rightarrow .\gamma'' A w''] \in \delta(q_0, \gamma')</math>. Pero aplicando la definición (3) de <math>\delta</math> por cada símbolo de <math>\gamma'</math> se ve que podemos llegar del estado <math>[B \rightarrow .\gamma'' A w'']</math> a <math>[B \rightarrow \gamma'' . A w'']</math> consumiendo <math>\gamma''</math>. Entonces, <math>[B \rightarrow \gamma'' . A w''] \in \delta(q_0, \gamma' \gamma'') = \delta(q_0, \gamma)</math> . Para terminar, por la def. (2), <math>[A \rightarrow .\alpha] \in \delta(\delta(q_0, \gamma), \lambda) = \delta(q_0, \gamma)</math>, como queríamos probar. | ||
** Ahora, con el lema probado si <math>[A \rightarrow \alpha . \beta]</math> es item válido para <math>\gamma</math>, entonces debe pasar que <math>[A \rightarrow . \alpha \beta]</math> es item válido para <math>\delta'</math> prefijo viable (con <math>\gamma = \delta' \alpha</math>)- Por el lema anterior , <math>[A \rightarrow . \alpha \beta] \in \delta(q_0, \delta') \Rightarrow</math> (usando la definición 3 de <math>\delta</math>) <math> [A \rightarrow \alpha . \beta] \in \delta(q_0, \delta' \alpha) = \delta(q_0, \gamma)</math> | ** Ahora, con el lema probado si <math>[A \rightarrow \alpha . \beta]</math> es item válido para <math>\gamma</math>, entonces debe pasar que <math>[A \rightarrow . \alpha \beta]</math> es item válido para <math>\delta'</math> prefijo viable (con <math>\gamma = \delta' \alpha</math>)- Por el lema anterior , <math>[A \rightarrow . \alpha \beta] \in \delta(q_0, \delta') \Rightarrow</math> (usando la definición 3 de <math>\delta</math>) <math> [A \rightarrow \alpha . \beta] \in \delta(q_0, \delta' \alpha) = \delta(q_0, \gamma)</math> | ||
=== Construccion de conjuntos de items === | === Construccion de conjuntos de items === |