[2014] [Segundo Parcial] [Ejercicio 4] [Parte a] Automatas de dos cintas

[2014] [Segundo Parcial] [Ejercicio 4] [Parte a] Automatas de dos cintas

de Juan Andres Nogueira Zunini -
Número de respuestas: 3

Hola, tengo una duda sobre los automatas de dos cintas.

En el parcial de 2014 en el ejercicio 4.a, el automata que proponen como solucion me parece que aceptaria el par de tiras <a,bbbbb>, lo cual no deberia ser un par de tiras validas segun la letra. Esto es asi o estoy entendiendo mal los automatas de dos cintas? 

Letra del parcial: https://www.fing.edu.uy/inco/cursos/teoleng/parciales/Parcial1-2014.pdf

Solucion: https://www.fing.edu.uy/inco/cursos/teoleng/parciales/SolParcial1-2014.pdf

Gracias!


En respuesta a Juan Andres Nogueira Zunini

Re: Automatas de dos cintas

de Mauricio Irace Perez -
Fijate que el loop de b's es de la primer cinta, por lo que <a,bbbbb> no seria aceptado
En respuesta a Mauricio Irace Perez

Re: Automatas de dos cintas

de Diego Garat -

hola:

tenés razón, el ciclo es en la primera cinta... pero por las dudas, aprovecho para aclarar otra cosa.  veamos la ejecución del autómata partiendo de  q0_2 con el par  <a,bbbbb>:


q0_2  <a,bbbbb>

--- consumo b de la seguna cinta

q0_1 <a, bbbb>

--- consumo a de la primera cinta

q2_1 < éps, bbbb>


como no hay más transiciones posibles ---q2_1 lee de la primera cinta y no quedan letras por consumir--- la máquina se detiene y da un resultado. ¿el autómata acepta o rechaza al par? 

si revisan la definición van a ver que no alcanza con llegar a un estado final sino que ambas componentes tienen que haber sido consumidas por completo para poder aceptar.  entonces, aunque estoy en el estado final q2_1, debo rechazar al par pues no terminé de consumir AMBAS cintas, me quedó "bbbb" en la segunda cinta por consumir.


saludos,

d.-