Edición de «Finales Virtuales: Diciembre - Marzo»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
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. | |||
== Septiembre == | |||
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. | |||
2) | |||
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 |