Finales Virtuales: Diciembre - Marzo

Los finales virtuales consistieron de uno o dos ejercicios 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 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, S_0, \Sigma, \Gamma, T, G)} que consiste de lo siguiente:

S es un conjunto finito de estados.

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_0 } es un estado inicial

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 \Sigma } es el alfabeto de entrada

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 \Gamma } es el alfabeto de salida

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 \delta }  : S 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 \times \Sigma \to S } es la función de transición

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 \gamma: S\times \Sigma \to \Gamma } 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 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 \delta } extendida y la función gamma extendida.

b) Demostrar que para todo autómata de pila determinístico P = 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 (Q, \Sigma, \gamma, \delta, q_0, Z_0, F) } 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 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 \Sigma} y 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 \Gamma} , ¿Cuántos autómatas de pila distintos 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 (Q, \Sigma, \delta, \Gamma, q_0, F)} 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

A-->a

A-->BCDE

A-->BC

donde A,B,C,D son no terminales, a es terminal. No se permiten producciones A->B ni A->BCE

Entonces son 4-2-Chomsky

S->ABCD

A->BDEF

A-> a

A->BC

No son 4-2-Chomsky

A->B

A-> ABC tampoco es 4-2-Chomsky

A-> abcedef 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 correctirud, 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 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 (Q, \Sigma, \delta, q_0, F)} ,

donde 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 \delta: Q\times Sigma \times N_0 \rightarrow Q} (donde 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 N_0} son los naturales con el 0).

Fijar un conjunto de estados Q de 4 estados y un alfabeto 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 \Sigma} de dos símbolos, valor máximo del contador M . Dar la cantidad de autómatas finitos determinísticos de esta clase.

b) Considerar autómata finito determinístico con una pila donde - Solo hay dos símbolos de pila, 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 Z } y 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 } . - 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 Z} está inicialmente en la pila. - El autómata puede reemplazar 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 Z_0} solo por 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^i Z } para 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 >= 0} - El autómata puede reemplazar 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} solo por 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^i} 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 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 (Q, \Sigma, \Gamma, \delta, q_0, F)} explicitando la función de transición delta.

Fijar un conjunto de estados Q de 4 estados y un alfabeto 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 \Sigma} 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 i <= c.

2) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma

A-->a

A-->BC

A-->BCD

No se permiten producciones A->B

donde A,B,C,D son no terminales, a es terminal.Entonces son 3-Chomsky

S-ABC

A->BDE

A-> a

A->BC

No son 3-Chomsky

A->B

A-> ABCDE tampoco es 3-Chmsky

A-> abcedef 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