Diferencia entre revisiones de «Finales Virtuales Tleng: Diciembre de 2020»
(Página creada con «Los finales virtuales consistieron de uno o dos ejercicios escritos que le eran asignados a cada persona que rendia particularmente, abajo estan la lista de preguntas que s…») |
Sin resumen de edición |
||
(No se muestra una edición intermedia del mismo usuario) | |||
Línea 82: | Línea 82: | ||
Fijar un conjunto de estados Q de 4 estados y un alfabeto <math>\Sigma</math> de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase. | Fijar un conjunto de estados Q de 4 estados y un alfabeto <math>\Sigma</math> de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase. | ||
7) Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c. | |||
(Adaptación del Lema 4.1 Aho-Ullman vol. 1). | |||
Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL.Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c. | |||
(Adaptación del Lema 4.1 Aho-Ullman vol. 1). | |||
Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL. |
Revisión actual - 17:17 19 abr 2021
Los finales virtuales consistieron de uno o dos ejercicios escritos que le eran asignados a cada persona que rendia particularmente, abajo estan la lista de preguntas que se tomaron en las distintas fechas.
Diciembre[editar]
1) Dar el algoritmo de minimizacion de autómatas finitos deterministicos, la demostracion de correctitud y su complejidad computacional.
2) Fijados los alfabetos y , ¿Cuántos autómatas de pila distintos determinístiscos hay, Si Q tiene 5 estados y en cada transición se escriben en la pila 0, 1 o 2 símbolos? ¿Y cuántos no determinísticos?
3) Demostrar que dada una gramática regular a derecha se puede obtener una gramática regular a izquierda equivalente. Tener en cuenta que disponemos del algoritmo para ir de gramática regular a derecha a autómata finito y que también disponemos del algoritmo para ir de autómata finito a gramática regular a derecha.
Hint: hallar la gramática del reverso de un lenguaje y el autómata finito del reverso de un lenguaje, o sea, dada G tal que L=L(G) hallar GR tal que LR=L(GR) y dado M tal que L=L(M) hallar MR tal que LR=L(MR), donde LR es el reverso del lenguaje L. Ayuda adicional: Hacer un ejemplo de gramática con 2 no terminales y 2 terminales y que genere una sola cadena.
4) Considerar la siguiente forma normal de 4-2-Chomsky donde todas las producciones son de la forma
donde A, B, C, D son no terminales, a es terminal.
No se permiten producciones ni
Entonces son 4-2-Chomsky
No son 4-2-Chomsky
tampoco es 4-2-Chomsky
tampoco es 4-2-Chomsky
Dar un algoritmo que pasa una gramatica libre de contexto a forma normal de 4-2-Chomsky Justificar correctitud.
Dar la complejidad computacional
5) Definir cuando una gramatica libre de contexto es recursiva a derecha. Dar el algoritmo de eliminación de recursión a derecha (inmediata y no inmediata), su justificación de correctitud, y su complejidad computacional.
6) a) Consideremos un autómata finito determinístico con un contador, que es un valor entero no negativo, que el autómata solamente pude distinguir entre cero y distinto de cero contadores. El movimiento de la máquina contador depende de su estado, símbolo de entrada y de si su contador es cero. En un movimiento la máquina contador puede: (a) Cambiar de estado. (b) Sumar o restar 1 a su contador.
Sin embargo, un contador no puede volverse negativo, por lo que no puede restar 1 de un contador que actualmente es 0.
El autómata es la tupla ,
donde (donde son los naturales con el 0).
Fijar un conjunto de estados Q de 4 estados y un alfabeto de dos símbolos, valor máximo del contador M. Dar la cantidad de autómatas finitos determinísticos de esta clase.
b) Considerar un autómata finito determinístico con una pila donde:
- Solo hay dos símbolos de pila, y .
- está inicialmente en la pila.
- El autómata puede reemplazar solo por para
- El autómata puede reemplazar solo por para i=0, 1, ó 2.
- Es decir, Z aparece solo en la parte inferior de cada pila, y todos los demás símbolos de pila, si los hay, son X.
Formalizar el autómata P como una tupla explicitando la función de transición delta.
Fijar un conjunto de estados Q de 4 estados y un alfabeto de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase.
7) Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c. (Adaptación del Lema 4.1 Aho-Ullman vol. 1). Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL.Sea G = (N, T, P, S) una gramática libre de contexto, no recursiva a izquierda y sin producciones A-> lambda. Existe una constante c tal que para todo par de símbolos no-terminales A,B, y para toda expresión α, si A => Bα entonces esta derivación se hace en una cantidad de pasos menor que c. (Adaptación del Lema 4.1 Aho-Ullman vol. 1). Ayuda: Este resultado se ua en la demostración de complejdida del algoritmo LL.