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

De Cuba-Wiki
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

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.

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_20/12/16_(Teoría_de_Lenguajes)&oldid=10883»