Creo que la solucion colgada no es correcta, aparecen cosas del ejercicio 4b
hola:
sí, hay dos máquinas de mealy cuando una, claramente, tendría que ser un afd2c.
saludos,
d.-
Tengo una duda con respecto a esta solución, que pasa si llega una tira de la forma <abbb,aabaa> en este caso el autómata consume aab de la 2da tira y luego consume toda la 1er tira quedando en el estado inicial. La duda es, como se chequea que cuando n=0 no hallan a's en la segunda tira? Gracias.
hola:
no hay nada por revisar: el par no es aceptado porque, aunque se llegó a un estado final, quedan símbolos por consumir en alguno de los componentes (en tu ejemplo, el segundo).
saludos,
d.-
Para comprobar que te entendí: Un automata finito determinista de dos cintas reconoce las tiras cuando una vez procesada la TOTALIDAD de las dos tiras se llega a un estado final?. Si llego a un estado final pero las tiras no se consumieron por completo entonces no es aceptada?
Dice la definición del práctico 4:
Un par de tiras (v, w) \in L(M) sii δ ́(q0, v, w) \in F.
luego, si quedan símbolos en alguna tira del par por procesar, el par no es aceptado, de la misma forma que un autómata finito "normal" no acepta una tira si llega a un estado final pero quedan símbolos por consumir.
Buenas, a mi también me quedan dudas respecto a este punto. En un AFD "una cinta", siempre se puede leer la entrada: al quedar el sistema en un estado cualquiera, la entrada se va a sacar del mismo lugar, la única cinta disponible. De donde siempre se va a vaciar esa cinta (teniendo en cuanta estados pozos implícitos), o sea toda la entrada.
Pero en un AFD2C, el estado final puede ser de la cinta 1, vaciándose esa cinta, pero puede todavía haber símbolos en la cinta 2 por leer.
En este caso, por la regla de (ej5):
"Cada estado está en uno de dos conjuntos dependiendo en que conjunto está el estado, el diagrama de transición se refiere a una u otra cinta."
la máquina no puede cambiar de estado está "trancada" en ese estado final a pesar de poder haber más símbolos en la otra cinta, ya que espera por entradas de la cinta 1, que está vacía. Un AFD1C nunca se "tranca", siempre se va a leer la totalidad de la entrada.
Hago notar esto porque me parece que hay una diferencias respecto al AFD1C, en la definición de "(w1,w2) son reconocidas por el autómata", se debería agregar que sí tiene que haberse leído la totalidad de las dos cintas, de otro modo en esta situación se cumple:
Un par de tiras (v, w) \in L(M) sii δ ́(q0, v, w) \in F
y quedan símbolos por procesar, y entonces según la definición igual el par es aceptado.
Incluso intentando agregar estados pozos después del estado final, se llega a esta misma situación, de indefinición. ¿Sobre que cinta tiene que estar el estado pozo?
¿O no?
Gracias.
hola:
la definición de recursiva de δ ́ implica, necesariamente, la lectura completa de la entrada, tanto en el caso de una como de dos cintas; δ ́(q0, (v, w)) pert F, implica que la lectura completa de ambas cintas lleva a un estado final. si el proceso de una entrada (v,w) el AFND-2C se traba sin consumir completamente alguna de las componentes, δ ́(q0, (v, w)) está indefinida.
"la
máquina no puede cambiar de estado está "trancada" en ese estado final a
pesar de poder haber más símbolos en la otra cinta, ya que espera por
entradas de la cinta 1, que está vacía." si el autómata se "tranca", el proceso se para y rechaza la entrada si le quedan símbolos por consumir. esto no es necesariamente un problema, sino, por el contrario, un efecto buscado. en el caso del ejercicio, las aes del final de la segunda cinta se corresponden con las primeras bes de la primera: luego de que se lee una a en la primera cinta, no debe quedar nada en la segunda para que la tira sea aceptada.
saludos,
d.-