Buenas, en el ejercicio 4 de este parcial, parte A, te pide hacer un autómata de 2 cintas. Tengo entendido que todo autómata tiene que consumir toda la/las cintas, por ende, me surge la pregunta de cómo interpreta el autómata de la solución la cinta <bbab, aabaa> (que no pertenece a L). Porque me queda una "a" que no se consume en la tira 2, sin embargo al ejecutar se queda en el estado q2_1 que es final.
[2014] [Segundo Parcial] [Ejercicio 4] [Parte a]
Número de respuestas: 5hola:
para aceptar un par de tiras es condición necesaria que el autómata haya consumido ambas cintas. si quedan símbolos en alguna de las dos y no hay forma de continuar su procesamiento, aunque estés en un estado final la tira no es aceptada.
lo mismo sucede en un AFD con función de transición parcial: si ustedes llegan a un estado en el que no hay transiciones para cierta entrada y queda entrada por consumir, la tira es rechazada aunque ese estado sea final.
saludos,
d.-
Gracias.
Este problema, no se puede resolver con un automata completo? De poderse, podrías dar un ejemplo?
(Pregunto para saber si todo autómata de dos cintas puede pasarse a uno completo de dos cintas)
hola:
para empezar, te diría que no se quiere. es mucho más claro un AF2C sin agregar estados auxiliares que no aportan al reconocimiento del par.
por otro, recordá que no tenés forma de detectar el "final de cinta" ---como tampoco lo podés hacer en un AF, en realidad--- con lo que no podés cambiar la lectura de la cinta consumida a un estado que procese la otra (la que te quedó con "porquería").
saludos,
d.-
Bien, última pregunta, todo AF de dos cintas se puede pasar a un AFC de dos cintas?
hola:
agregando una marca de fin de tira, sí se podría hacer fácilmente.
con el modelo visto en clase, no sabría decirte a ciencia cierta ---tendría que demostrarlo--- pero tiendo a pensar que no; en todo caso no sería algo tan sencillo como completar el caso AFD. en ambos casos tampoco tendría un sentido práctico, salvo que estés pensando en probar la clausura bajo complemento :)
saludos,
d.-