Edición de «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 <math>\Sigma</math> y <math>\Gamma</math>,
¿Cuántos autómatas de pila distintos <math>(Q, \Sigma, \delta, \Gamma, q_0, F)</math> 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

<math> A \rightarrow a </math>

<math> A \rightarrow BCDE </math>

<math> A \rightarrow BC </math>

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

No se permiten  producciones <math> A \rightarrow B </math> ni <math>A \rightarrow BCE </math>

Entonces  son 4-2-Chomsky

<math> S \rightarrow ABCD </math>

<math> A \rightarrow BDEF </math>

<math> A \rightarrow a </math>

<math> A \rightarrow BC </math>

No son 4-2-Chomsky

<math> A \rightarrow B </math>

<math> A \rightarrow ABC </math> tampoco es 4-2-Chomsky

<math> A \rightarrow abcedef </math>  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  <math>(Q, \Sigma, \delta, q_0, F)</math>, 

donde <math>\delta: Q\times Sigma \times N_0 \rightarrow Q</math>
(donde <math>N_0</math> son los naturales con el 0).

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

-  <math>Z</math> está inicialmente en la pila.

-  El autómata puede reemplazar <math>Z_0</math> solo por <math>X^i Z </math> para <math>i >= 0</math>

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

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 \Rightarrow 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 \Rightarrow 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.