[Ejercicio 3]

[Ejercicio 3]

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

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
En respuesta a Santiago Gongora

Re: Ejercicio3

de Facundo Rodríguez Martínez -
Hola (un poco tarde), viendo estas respuestas me surge una duda cuando diego dice acerca de "duplicar estados" para contemplar el caso donde la última ficha sale por D. Otra alternativa podría ser agregar un solo estado nuevo D que sea el final? En esta situación, cada caso donde las posiciones de las llaves hagan que la ficha caiga a D tendríamos una flecha hacia D, además de al siguiente estado de las llaves. Si todavía hay fichas por computar, entonces del estado D irían a un estado pozo, esto está bien?

Gracias
En respuesta a Facundo Rodríguez Martínez

Re: Ejercicio3

de Diego Garat -
hola:

la entrada es una secuencia de fichas, y los estados van cambiando de acuerdo a las reglas del juego cada vez que se procesa una ficha (letra). al procesar una tira, se puede dejar al juego en una misma configuración de puertas, pero saliendo por distintas ramas. eso hace que una misma configuración del juego pueda ser al mismo tiempo ganador o no ganadora según la ficha. si mi opción fue modelar la configuración del juego como un estado, debo contemplar entonces las mismas compuertas para los dos casos (ficha ganadora/perdedora).

¿qué sucede si agrego un nuevo estado final? en principio no habría problema, pero el autómata sería no determinista. la solución propuesta te da, directamente un AFD.

saludos,
d.-
En respuesta a Diego Garat

Re: Ejercicio3

de Facundo Rodríguez Martínez -
Perdón. no estoy seguro de haber entendido bien tu respuesta.
Me quedó un AFND, que, cada estado es una posición de llaves, según un 1 o 0 me muevo al siguiente estado, pero además, en los casos donde caiga por D, también hay una transición a D (estado final válido). Pero no dupliqué ningún estado como vos dijiste a anteriormente. Esto está bien?
 
Lo muestro a continuación:

image.png

Gracias
En respuesta a Facundo Rodríguez Martínez

Re: Ejercicio3

de Diego Garat -
hola:

normalmente no corregimos soluciones por esta vía. como te decía, sí, es posible hacer un AFND con un único estado final. si lo pasás a AFD, se te van a duplicar los estados.

agregar el estado pozo es innecesario, sobre todo si tu autómata es no determinista, pero si lo hacés, tenés que agregar las transiciones de P al propio P.

saludos,
d.-