MT Diciembre 2014

MT Diciembre 2014

de Ignacio Daniel Vigna López -
Número de respuestas: 2

Hola, la consulta es sobre el ejercicio 1 del examen Diciembre 2014 (https://www.fing.edu.uy/inco/cursos/teoleng/examenes/ST-Diciembre2014.pdf)

¿Puede ser que falte en la solución en la transición del estado q4 al q2 la transición 1,1,Izq? Además de la 0,1,Izq que ya tiene.

En particular para el caso en que tengo dos tiras con igual cantidad de dígitos entre los ## por ejemplo: aaaa#aaaa.

Ya de paso también quería preguntar por qué es que este autómata no tiene ningún estado final y si no es obligatorio ponerlo en este tipo de MT que computan funciones (pienso que en este caso una vez computada la función lo que pasa es que terminas en un estado pozo que no está puesto y por eso no se rompe, pero igual me gustaría saber si es correcto esto).

Muchas gracias

En respuesta a Ignacio Daniel Vigna López

Re: MT Diciembre 2014

de Diego Garat -

hola:


sí, efectivamente de q4 a q2 estaría faltando la transición que mencionás: el autómata falla cuando hay dos subsecuencias de igual largo.

además, en principio, le estaría faltando un estado final a esa máquina... pero como es una MT que computa funciones, y en q0 se produce un salto cuando solo hay una tira de ceros y unos, se podría considerar como correcta (lo que queda en la cinta es, efectivamente, el resultado de computar la función). yo prefiero el modelo que explícitamente da por terminada la computación con un estado final y en ese caso es tan simple como agregar un nuevo estado y transiciones que salen de q0 a ese estado final con los símbolos 0 o 1 en la cinta. 

saludos,

d.-