Finales virtuales: Diciembre-Marzo

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.