Final del 20/12/16 (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar

Escrito, tomado por Julio Jacobo y Jose Castaño

Ejercicio 1[editar]

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[editar]

Demostrar el lema de pumping para lenguajes libres de contexto.

Ejercicio 3[editar]

Demostrar que el lenguaje ww no es libre de contexto. Sugerencia: considerar una cadena a...ab...ba...ab...b perteneciente al lenguaje.

Ejercicio 4[editar]

Definir PRIMEROS y SIGUIENTES e indicar en qué algoritmos de parsing se usan y cómo, o explicar parsing no determinístico.