Final del 19/05/17 (Teoría de Lenguajes)

El final fue tomado por Julio Jacobo. Éramos 4 así que tomó oral, 40 minutos cada uno aproximadamente.

• Final 1:

1) Demostrar equivalencia entre Grámatica regular y AFND, incluyendo los lemas.

2) Demostrar que dado M autómata de pila por estado final, existe M' automata de pila por pila vacia

3) Explicar LR. Hacer el diagrama de Venn (Para esto está bueno decir que los parsers vistos son para lenguajes independientes de contexto determinísticos).

• Final 2:

1) Demostrar pasaje de Expresión regular y AFND.

2) Demostrar pasaje de AFD a Expresión regular.

3) Dar las propiedades de los lenguajes libres de contexto sobre unión, concatenación y clausura de Kleene. Mostrar un contraejemplo para la intersección.

4) Enunciar y demostrar el Lema de Pumping para lenguajes libres de contexto.

• Final 3:

1) Demostrar pasaje de AFND a AFD incluyendo el lema.

2) Dar las propiedades de los lenguajes libres de contexto.

3) Explicar LL.