|
|
| 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]] |
| *[[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]] | | *[[Finales Virtuales Tleng: Marzo de 2020 | Marzo de 2021]] |
| | |
| == 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
| |
