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

De Cuba-Wiki
Revisión del 18:39 21 dic 2016 de Mangostia (discusión | contribs.) (Página creada con «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ínim...»)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

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.