Finales Virtuales: Diciembre - Marzo

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.

• Septiembre de 2020

Septiembre

1)

a) Consideremos el transductor finito dado por una máquina de Mealy $(S,S_{0},\Sigma ,\Gamma ,T,G)$ que consiste de lo siguiente:

S es un conjunto finito de estados.

$S_{0}$ es un estado inicial

$\Sigma$ es el alfabeto de entrada

$\Gamma$ es el alfabeto de salida

$\delta$ : S $\times \Sigma \to S$ es la función de transición

$\gamma :S\times \Sigma \to \Gamma$ mapea un estado y un símbolo de entarda a un símbolo de salida.

Definir la relación de equivalencia de estados usado en para el algoritmo de minimizacion considerando la función $\delta$ extendida y la función gamma extendida.

b) Demostrar que para todo autómata de pila determinístico P = $(Q,\Sigma ,\gamma ,\delta ,q_{0},Z_{0},F)$ hay otro P′ tal que L(P) = L(P′) y P′ no tiene configuraciones que ciclen.

Ayuda: Dar primero la definición de configuración que cicla

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.

Marzo

1) Si S es una GLC no Recursiva a izquierda. Entonces para toda producción A y B en S con A => Bα, la cantidad de pasos de derivación i está acotada por una constance c, es decir $i\leq c$.

2) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma

$A\rightarrow a$

$A\rightarrow BC$

$A\rightarrow BCD$

No se permiten producciones $A\rightarrow B$

donde A, B, C, D son no terminales, a es terminal. Entonces son 3-Chomsky

$S\rightarrow ABC$

$A\rightarrow BDE$

$A\rightarrow a$

$A\rightarrow BC$

$A\rightarrow BC$

No son 3-Chomsky

$A\rightarrow B$

$A\rightarrow ABCDE$ tampoco es 3-Chmsky

$A\rightarrow abcedef$ tampoco es 3-Chomsky

Dar un algoritmo que pase una gramatica libre de contexto a forma normal 3-Chomsky.

Dar la complejidad computacional.

3) Dar un algoritmo que transforme cada gramatica libre de contexto G en otra G' que reconoce el mismo lenguaje pero es tal que si $X_{1}...X_{k}$ es el lado derecho de una producción entonces todos los símbos $X_{1}..X_{k}$ son distintos.

Justificar la correctitud y Dar la complejidad del algoritmo

Poner varios ejemplos

4) a) Determinar Verdadero o Falso y dar la demostración:

a- Para todo automata de pila no deterministico existe otro deterministico equivalente, es decir, que reconoce exactamente el mismo lenguaje.

b- Para todo automata de pila deterministico existe otro equivalente que siempre consume toda la entrada.

c- Si un lenguaje es libre de contexto su complemento también

b) Determinar Verdadero o Falso y dar la demostración:

a- Para todo automata de pila no deterministico existe otro deterministico equivalente, es decir, que reconoce exactamente el mismo lenguaje.

b- Para todo automata de pila deterministico existe otro equivalente que siempre consume toda la entrada.

c- Si un lenguaje es libre de contexto su complemento también