Final del 12/09/14 (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 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 infinitas 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 de longitud arbitraria, pero si llego a probar todas las cadenas de hasta 2n y no encontré ninguna > n aceptada, entonces no acepta ninguna otra > n. 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).