Diferencia entre revisiones de «Resolución Final del 13/06/23 (Teoría de Lenguajes)»
(Página creada con «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 convierte en llevar transformarlo a un autómata determinístico. El algoritmo quedaría de la siguie…») |
Sin resumen de edición |
||
| (No se muestran 2 ediciones intermedias de 2 usuarios) | |||
| Línea 3: | Línea 3: | ||
==== Ej 1 ==== | ==== 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 | 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: | El algoritmo quedaría de la siguiente manera: | ||
| Línea 9: | Línea 9: | ||
OUTPUT: AFND-lambda A' codeterminístico. | OUTPUT: AFND-lambda A' codeterminístico. | ||
* Tomar reverso de A | * Tomar reverso de <math>A</math> | ||
* Hacer pasaje de <math>A^r</math> a un autómata determinístico | * Hacer pasaje de <math>A^r</math> a un autómata determinístico | ||
* Tomar reverso de <math>A^r</math> | * Tomar reverso de <math>A'\ ^r</math> | ||
El autómata A' resultante reconoce el lenguaje original. | El autómata <math>A'</math> resultante reconoce el lenguaje original. | ||
==== Ej 2 ==== | ==== 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 <math>A\rightarrow_L^* B\alpha</math>, se puede pasar a lo sumo una vez por cada no terminal. La cota resulta en <math>|V_n|-1</math> | 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 <math>A\rightarrow_L^* B\alpha</math>, se puede pasar a lo sumo una vez por cada no terminal. La cota resulta en <math>|V_n|-1</math> | ||
Revisión actual - 05:19 18 jun 2023
Idea de resolución de los ejercicios
Ej 1[editar]
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
- Hacer pasaje de a un autómata determinístico
- Tomar reverso de
El autómata resultante reconoce el lenguaje original.
Ej 2[editar]
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 , se puede pasar a lo sumo una vez por cada no terminal. La cota resulta en
