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.