DFA pour les lancers de pièces attendus

Question

Je tente de construire ce problème:

Une pièce de monnaie juste est lancée jusqu'à ce que deux têtes apparaissent dans une rangée. Quel est le nombre attendu de lancers de pièces de monnaie? Concevoir un DFA pour le langage L + {w | w a 11 comme sous-chaîne}

Utilisez cette DFA comme chaîne de Markov pour calculer la probabilité requise. (Spécifiquement pour chaque état q, soit P (q) la probabilité d'atteindre l'état acceptant, si q est l'état initial.)

J'ai des difficultés à concevoir le DFA et j'ai besoin d'aide.

Answer 1

Un indice:

Je prends la langue pour se composer de toutes les chaînes binaires qui ont 11 en tant que sous-chaîne. Par exemple, 01001101 est dans la langue mais 10100010 ne l'est pas. Vous pouvez le faire avec seulement 3 états. Pensez aux états comme correspondant à la distance du but (acceptant l'état) d'avoir 2 uns dans une rangée. Vous commencez loin de cet état. Si vous lisez un 0 vous restez loin de cet état. Si vous lisez un 1 alors vous passez à l'état d'être presque là. Si vous êtes dans cet état presque là - que se passe-t-il lorsque vous lisez un 0? Que se passe-t-il lorsque vous lisez un 1? Enfin - une fois que vous y arrivez, vous êtes dans l'état heureux d'être fait et aucune entrée ne vous ramènera à un état antérieur.