Final del 12/09/14 (Teoría de Lenguajes)

De Cuba-Wiki
Revisión del 19:34 12 sep 2014 de Mauricio (discusión | contribs.) (Página creada con «{{Back|Teoría de Lenguajes}} Todo oral, se puede usar pizarrón, los docentes ayudan si uno va por mal camino. Las demostraciones son a grandes rasgos, sin entrar en deta...»)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Plantilla:Back

Todo oral, se puede usar pizarrón, los docentes ayudan si uno va por mal camino. Las demostraciones son a grandes rasgos, sin entrar en detalles de formalismo.

  • 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 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 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).