Edición de «Final del 12/09/14 (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 5: | Línea 5: | ||
* Enunciar y demostrar pumping para lenguajes regulares. | * Enunciar y demostrar pumping para lenguajes regulares. | ||
* Se tiene un AFD al que se le conoce su alfabeto y la cantidad de estados n y se lo puede usar como una caja negra a la que le puedo pasar cadenas y retorna si la acepta o no. ¿Cuál es la longitud máxima de cadena que necesito pasarle para convencerme de que acepta o no infinitas | * Se tiene un AFD al que se le conoce su alfabeto y la cantidad de estados n y se lo puede usar como una caja negra a la que le puedo pasar cadenas y retorna si la acepta o no. ¿Cuál es la longitud máxima de cadena que necesito pasarle para convencerme de que acepta o no cadenas infinitas? | ||
Respuesta: con probar con todas las cadenas posibles de longitud hasta el doble de la cantidad de estados alcanza, ya que si encuentro una sola de longitud > n que es aceptada entonces acepta cadenas | Respuesta: con probar con todas las cadenas posibles de longitud hasta el doble de la cantidad de estados alcanza, ya que si encuentro una sola de longitud > n que es aceptada entonces acepta cadenas infinitas, pero si llego a probar todas las cadenas de hasta 2n y no encontré ninguna > n aceptada, entonces no acepta ninguna cadena infinita. El razonamiento es similar al usado para demostrar pumping. | ||
* Explicar cómo es tabla de LR y el algoritmo LR (en general para cualquier versión de LR, asumiendo que ya se tiene la tabla creada). | * Explicar cómo es tabla de LR y el algoritmo LR (en general para cualquier versión de LR, asumiendo que ya se tiene la tabla creada). | ||
[[Category:Finales]] | [[Category:Finales]] |