Finales Virtuales Tleng: Septiembre de 2020

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.

Septiembre

1)

a) Consideremos el transductor finito dado por una máquina de Mealy $(S,S_{0},\Sigma ,\Gamma ,T,G)$ que consiste de lo siguiente:

S es un conjunto finito de estados.

$S_{0}$ es un estado inicial

$\Sigma$ es el alfabeto de entrada

$\Gamma$ es el alfabeto de salida

$\delta$ : S $\times \Sigma \to S$ es la función de transición

$\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 $\delta$ extendida y la función gamma extendida.

b) Demostrar que para todo autómata de pila determinístico P = $(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