Resolución Final del 13/06/23 (Teoría de Lenguajes)

Idea de resolución de los ejercicios

Ej 1

Un autómata es codeterminístico si no hay dos estados que apunten con el mismo caracter a un tercer estado. Si se da este caso, al invertir la dirección de las flechas, este estado tendría dos transiciones distintas a través de un mismo caracter. Por lo tanto, al tomar el reverso del autómata el problema se reduce a obtener el autómata determinístico equivalente. El algoritmo quedaría de la siguiente manera:

INPUT: AFND-lambda A no codeterminístico.
OUTPUT: AFND-lambda A' codeterminístico.

• Tomar reverso de A
• Hacer pasaje de $A^{r}$ a un autómata determinístico
• Tomar reverso de $A'^{r}$

El autómata A' resultante reconoce el lenguaje original.

Ej 2

Es una versión simplificada de la demostración de la cota para el algoritmo de parsing LL(1). La idea sería que, como el lenguaje no es recursivo a izquierda, no es posible que se genere una derivación en donde se repita un no terminal en la izquierda. Por lo tanto, para llegar a la derivación $A\rightarrow _{L}^{*}B\alpha$, se puede pasar a lo sumo una vez por cada no terminal. La cota resulta en $|V_{n}|-1$