Autor Tema: Juego de Marble: Ejercicio Hopcroft

0 Usuarios y 1 Visitante están viendo este tema.

11 Junio, 2014, 08:43 pm
Leído 1547 veces

juaninf

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 296
  • Karma: +0/-0
  • Sexo: Masculino
  • dale : http://juaninf.blogspot.com
Estoy resolviendo  un ejercicio del libro Hopcroft and *et al*. La Figura 1 abajo es un juego denominado objeto rolling-toy. El objeto se puede dejar caer en las entradas A o B. Los interruptores \( x_1,x_2 \) y \( x_3 \) hacen que el objeto caiga en C o en D. Cada vez que el objeto encuentra un interruptor, causa que el interruptor cambie de estado, asi el proximo objeto que pase por el tomara un sentido diferente.



El ejercicio tiene 3 tres preguntas de las cuáles he conseguido resolver dos. Las preguntas son las siguientes:

a)Modelar este juego con un automata finito: Una secuencia de objetos es aceptada si el último objeto cae en D: Para modelar el juego, un estado es representado como una secuencia de tres bits que representan los interruptores seguido de r o a (del inglés rejected o accepted). Por ejemplo, 010a, significa izquierda, derecha, izquierda, aceptado. Entonces tenemos que la tabla de transición es



Ahora, mi problema es
b) Informalmente describir el lenguaje del automata: Consigo ver que acontece cuando los objetos son secuencias que solo caen en A o solo caen en B, es decir secuencias del tipo A* y B* pero no encuentro alguna regla para las secuencias que tiene los dos simbolos