[Ejercicio 3]

[Ejercicio 3]

de Juan Manuel Tassino Chaparro -
Número de respuestas: 4

Buenas, estuve viendo este ejercicio un rato y no pude encontrar bien la manera de modelarlo, tengo la idea de que tiene algo que ver con la paridad de las entradas anteriores por A y por B, pero no encontrarle la vuelta. Es con un AFND, ¿no? ¿Cómo podemos darnos cuenta fácil de que tipo de autómata tenemos que hacer?

Gracias, saludos
Juan.


En respuesta a Juan Manuel Tassino Chaparro

Re: Ejercicio3

de Diego Garat -
hola:

creo que en vez de pensarlo por paridad, lo más fácil es directamente modelar el juego con las reglas dadas:

el estado del juego está dado por la configuración de las llaves. así, (x: <, y:<), (x:<, y:>), (x:<, y:<) serían algunos estados del autómata. por ejemplo, el estado del dibujo sería (>,<). si yo pongo en ese estado una ficha por A (leo un 1), el siguiente estado sería (>,>), ya que solo cambia el valor de y.

luego, ¿qué sucede con la aceptación de la tira? para eso hay que considerar que si sale por D, el estado resultante debería ser final... con lo que se pueden duplicar tus estados. por ejemplo, podrías tener un estado (<,<) y otro ((<,<)) para indicar que en un caso la última ficha salió por C y en el otro por D, dejando  el juego en la configuración x:< e y:<.

saludos,
d.-





creo que no es necesario usar un AFND, dado que, puesta una ficha por A o B, la configuración resultante está determinada.
En respuesta a Diego Garat

Re: Ejercicio3

de Santiago Gongora -
Complemento la respuesta de Diego pero focalizándome en tu otra pregunta "¿Cómo podemos darnos cuenta fácil de que tipo de autómata tenemos que hacer?"

Capaz que Diego, que tiene mucha más experiencia que yo, puede darte alguna regla más precisa sobre qué modelo usar para razonar un problema.

Lo que yo puedo aportar es que en general, el AFND nos sirve para aquellos casos donde "no estamos seguros cuándo dejar de reconocer un patrón para pasar a reconocer el otro". Por ejemplo, para construir un AF que reconozca el lenguaje L((a|b)^*bab), a priori no sabríamos cómo decidirnos si una "b" leída corresponde a L((a|b)^*) o a L((bab). Ahí es que vamos a tener dos transiciones con el símbolo "b", una que siga reconociendo el primer patrón y otra que comience a reconocer el segundo. Tener más de una transición desde el mismo estado con el mismo símbolo es lo que genera el no determinismo.

Demás está decir que, por lo que muestra JJ en el teórico, si existe un AFND que reconozca a un lenguaje también existe un AFD que lo haga. El asunto acá es qué es lo más fácil de razonar, si el AFND o el AFD.

Por ejemplo, para el caso que puse arriba, es claramente más fácil hacer un AFND y luego, si quisiéramos un AFD, pasarlo usando el algoritmo visto en el teórico.

Hay un poco más de desarrollo sobre estas ideas en el segundo documento de AF que subimos pero, como siempre, cualquier cosa a las órdenes.

Saludos,
Santi