|
|
| Línea 3: |
Línea 3: |
| *[[Finales Virtuales Tleng: Septiembre de 2020 | Septiembre de 2020]] | | *[[Finales Virtuales Tleng: Septiembre de 2020 | Septiembre de 2020]] |
| *[[Finales Virtuales Tleng: Diciembre de 2020 | Diciembre de 2020]] | | *[[Finales Virtuales Tleng: Diciembre de 2020 | Diciembre de 2020]] |
| | | *[[Finales Virtuales Tleng: Marzo de 2020 | Marzo de 2020]] |
| == 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 == | | == 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.
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 
.
2) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma
No se permiten producciones 
donde A, B, C, D son no terminales, a es terminal. Entonces son 3-Chomsky
No son 3-Chomsky
tampoco es 3-Chmsky
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 
es el lado derecho de una producción entonces
todos los símbos 
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
