Diferencia entre revisiones de «Finales Virtuales: Diciembre - Marzo»

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
 
(No se muestran 3 ediciones intermedias del mismo usuario)
Línea 1: Línea 1:
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.
Abajo estan listados las diferentes preguntas escritas que se tomaron en los correspondientes meses.


*[[Finales Virtuales Tleng: Septiembre de 2020 | Septiembre de 2020]]
*[[Finales Virtuales Tleng: Septiembre de 2020 | Septiembre de 2020]]
== Septiembre ==
*[[Finales Virtuales Tleng: Diciembre de 2020 | Diciembre de 2020]]
 
*[[Finales Virtuales Tleng: Marzo de 2021 | Marzo de 2021]]
1)
 
a) Consideremos el transductor finito dado por una máquina de Mealy
<math>(S, S_0, \Sigma, \Gamma, T, G)</math>
que consiste de lo siguiente:
 
S es un conjunto finito de estados.
 
<math>S_0 </math> es un estado inicial
 
<math>\Sigma </math> es el alfabeto de entrada
 
<math> \Gamma </math>  es el alfabeto de salida
 
<math> \delta </math> : S <math> \times \Sigma \to S </math> es la función de transición
 
<math>  \gamma: S\times \Sigma \to \Gamma </math>
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 <math>\delta </math> extendida y la función gamma extendida.
 
b) Demostrar que para todo autómata de pila determinístico  P = <math> (Q, \Sigma, \gamma, \delta, q_0,  Z_0, F) </math> 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 <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.
 
== 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 <math>i \leq  c </math>.
 
2) Considerar la siguiente forma normal de 3-Chomsky donde todas las  producciones son de la  forma
 
<math> A \rightarrow a </math>
 
<math> A \rightarrow BC </math>
 
<math> A \rightarrow BCD </math>
 
No se permiten  producciones <math> A \rightarrow B </math>
 
donde A, B, C, D  son no terminales,  a es terminal. Entonces  son 3-Chomsky
 
<math>S \rightarrow ABC</math> 
<math> A \rightarrow BDE </math>
 
<math> A \rightarrow a </math>
 
<math> A \rightarrow BC </math>
 
<math> A \rightarrow BC </math>
 
No son 3-Chomsky
 
<math> A \rightarrow B </math>
 
<math> A \rightarrow ABCDE </math> tampoco es 3-Chmsky
 
<math> A \rightarrow abcedef </math> 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 <math>X_1... X_k</math> es el lado derecho de una producción entonces
todos los símbos <math>X_1..X_k</math> 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

Revisión actual - 22:49 4 mar 2021

Abajo estan listados las diferentes preguntas escritas que se tomaron en los correspondientes meses.