DFA für erwartete Münzwürfe

Question

Ich versuche dieses Problem zu konstruieren:

Eine faire Münze wird geworfen, bis zwei Köpfe in einer Reihe erscheinen. Was ist die erwartete Anzahl von Münzwürfen? Entwerfen eines DFA für die Sprache L + {w | w hat 11 als Teilzeichenfolge}

Verwenden Sie dieses DFA als Markov-Kette, um die erforderliche Wahrscheinlichkeit zu berechnen. (Speziell für jeden Zustand q sei P (q) die Wahrscheinlichkeit, den akzeptierenden Zustand zu erreichen, wenn q der Startzustand ist.)

Ich habe Probleme beim Entwerfen des DFA und benötige Hilfe.

Answer 1

Ein Tipp:

Ich nehme die Sprache aller Binärketten bestehen, die 11 als Teil haben. Zum Beispiel ist 01001101 in der Sprache, aber 10100010 ist nicht. Sie können dies mit nur 3 Zuständen tun. Stellen Sie sich die Zustände so vor, als ob sie der Entfernung vom Ziel (akzeptierender Zustand) entsprechen, wenn Sie zwei hintereinander haben. Du fängst weit von diesem Zustand an. Wenn Sie eine 0 lesen, bleiben Sie weit von diesem Zustand entfernt. Wenn Sie eine 1 lesen, dann wechseln Sie in den Zustand fast dort. Wenn Sie sich in diesem Zustand befinden - was passiert, wenn Sie eine 0 lesen? Was passiert, wenn Sie eine 1 lesen? Endlich - wenn du erst einmal da bist, bist du in einem glücklichen Zustand und keine Eingabe wird dich in einen früheren Zustand zurückversetzen.