Final del 20/12/16 (Teoría de Lenguajes)
De Cuba-Wiki
Escrito, tomado por Julio Jacobo y Jose Castaño
Ejercicio 1
Demostrar que el AFD mínimo construido según el criterio de indistinguibilidad es efectivamente mínimo (es decir, demostrar que si hubiese otro AFD que aceptase el mismo lenguaje entonces este tendría a lo sumo la misma cantidad de estados que el mínimo).
Ejercicio 2
Demostrar el lema de pumping para lenguajes libres de contexto.
Ejercicio 3
Demostrar que el lenguaje ww no es libre de contexto. Sugerencia: considerar una cadena a...ab...ba...ab...b perteneciente al lenguaje.
Ejercicio 4
Definir PRIMEROS y SIGUIENTES e indicar en qué algoritmos de parsing se usan y cómo, o explicar parsing no determinístico.
