Finales Virtuales Tleng: Diciembre de 2020

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

1) Dar el algoritmo de minimizacion de autómatas finitos deterministicos, la demostracion de correctitud y su complejidad computacional.

2) Fijados los alfabetos $\Sigma$ y $\Gamma$, ¿Cuántos autómatas de pila distintos $(Q,\Sigma ,\delta ,\Gamma ,q_{0},F)$ 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

$A\rightarrow a$

$A\rightarrow BCDE$

$A\rightarrow BC$

donde A, B, C, D son no terminales, a es terminal.

No se permiten producciones $A\rightarrow B$ ni $A\rightarrow BCE$

Entonces son 4-2-Chomsky

$S\rightarrow ABCD$

$A\rightarrow BDEF$

$A\rightarrow a$

$A\rightarrow BC$

No son 4-2-Chomsky

$A\rightarrow B$

$A\rightarrow ABC$ tampoco es 4-2-Chomsky

$A\rightarrow abcedef$ 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 $(Q,\Sigma ,\delta ,q_{0},F)$,

donde $\delta :Q\times Sigma\times N_{0}\rightarrow Q$ (donde $N_{0}$ son los naturales con el 0).

Fijar un conjunto de estados Q de 4 estados y un alfabeto $\Sigma$ 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, $Z$ y $X$.

- $Z$ está inicialmente en la pila.

- El autómata puede reemplazar $Z_{0}$ solo por $X^{i}Z$ para $i>=0$

- El autómata puede reemplazar $X$ solo por $X^{i}$ 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 $(Q,\Sigma ,\Gamma ,\delta ,q_{0},F)$ explicitando la función de transición delta.

Fijar un conjunto de estados Q de 4 estados y un alfabeto $\Sigma$ 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.