[Ejercicio 1] [Parte 4] Duda general

[Ejercicio 1] [Parte 4] Duda general

de Valentina Pereira Ciaffone -
Número de respuestas: 3

Buenas!

Haciendo el 1.4 me surgió la siguiente duda, al necesitar imprimir dos d por cada b.

Por el teórico y una pregunta del foro yo tenia entendido que Moore y Mealy son AFD (son un caso particular de dos cintas).

Pero acá me vi en la necesidad de una de estas dos cosas:

1. Poder imprimir mas de un carácter por vez.

2. Necesito consumir la tira vacía -> transiciones épsilon.

La 1era la descarte por como esta definida la función lambda.

La segunda me marea, y la vi en la solución de examen Feb2021 Ej1B pero no entiendo como teniendo transiciones épsilon el autómata sigue siendo un AFD. 

Espero se entienda, 

Saludos!


En respuesta a Valentina Pereira Ciaffone

Re: Ej1.4 (duda general)

de Diego Garat -

hola:

moore, mealy y AF2C son autómatas que modelan relaciones entre tiras, y se pueden ver como máquinas que reconocen, de una forma u otra, pares tiras. sin embargo, su funcionamiento (y alcance) es distinto y no las consideramos de igual forma en el curso.

el modelo de AF2C que se define en el teórico y usamos en el práctico es determinista: no hay transiciones épsilon, no hay varias posibles transiciones desde un mismo estado para un mismo símbolo. en todas las evaluaciones se pueden resolver los problemas de AF2C con este modelo, sin excepciones.

en cambio, no todos los problemas que se plantean de máquinas con salida se pueden resolver con el modelo visto en el teórico. por ejemplo, si el par entrada y su correspondiente salida tienen distintos largo, seguramente ya no te sirve ese modelo tan estricto.

por eso en el práctico (y las evaluaciones) se les permite extender el modelo de forma tal que las transiciones pueden no leer la entrada o pueden no imprimir salida (pero no ambas en una misma transición).

el modelo resultante, efectivamente, deja de ser estrictamente determinista.


saludos,

d.-




En respuesta a Diego Garat

Re: Ej1.4 (duda general)

de Valentina Pereira Ciaffone -
Se entendio, muchas gracias.
Pero me quedo otra duda, en ese caso si me queda un grafo con una arista epsilon/salida como en el de el examen, como aplico el algoritmo para pasar de mealy a moore?
Ya no puedo hacer el delta de ese estado con los simbolos de entrada, porque para el unico simbolo que tiene arista es epsilon. Obvio los otros y me quedo con ese?