Diferencia entre revisiones de «Finales Virtuales Tleng: Marzo de 2021»
(Página creada con «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 s…») |
(Agregar que la derivacion es la más a la izquierda (IMPORTANTE). Agregar latex) |
||
Línea 3: | Línea 3: | ||
== 01/03 == | == 01/03 == | ||
1) Si S es una GLC no Recursiva a izquierda. Entonces para | 1) Si S es una GLC no Recursiva a izquierda. Entonces para todo par de no terminales A y B en S con <math> A \rightarrow_L B \alpha </math> una derivación más a la izquierda, la cantidad de pasos de derivación i está acotada por una constante 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 | 2) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma |
Revisión del 17:11 8 mar 2021
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.
01/03
1) Si S es una GLC no Recursiva a izquierda. Entonces para todo par de no terminales A y B en S con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow_L B \alpha } una derivación más a la izquierda, la cantidad de pasos de derivación i está acotada por una constante c, es decir Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i \leq c } .
2) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BCD }
No se permiten producciones Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B }
donde A, B, C, D son no terminales, a es terminal. Entonces son 3-Chomsky
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \rightarrow ABC}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BDE }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }
No son 3-Chomsky
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow ABCDE } tampoco es 3-Chmsky
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow abcedef } tampoco es 3-Chomsky
Dar un algoritmo que pase una gramatica libre de contexto a forma normal 3-Chomsky.
Dar la complejidad computacional.
04/03
1) Dar un algoritmo que transforme cada gramatica libre de contexto G en otra G' que reconoce el mismo lenguaje pero es tal que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X_1... X_k} es el lado derecho de una producción entonces todos los símbos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X_1..X_k} son distintos.
Justificar la correctitud y Dar la complejidad del algoritmo
Poner varios ejemplos
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