DFA для ожидаемых монетных моментов

Question

Я пытаюсь решить эту проблему:

Справедливая монета бросается до тех пор, пока две главы не появятся в ряду. Каково ожидаемое количество монетных бросков? Проектирование DFA для языка L + {w | w имеет 11 в качестве подстроки}

Используйте этот DFA в качестве цепи Маркова для расчета требуемой вероятности. (В частности, для каждого состояния q, P (q) - вероятность достижения принимающего состояния, если q является начальным состоянием.)

У меня возникли проблемы с проектированием DFA и вам нужна помощь.

Answer 1

Подсказка:

Я беру язык состоит из всех двоичных строк, которые имеют 11 в качестве подстроки. Например, 01001101 находится на этом языке, но 10100010 - нет. Вы можете сделать это всего за 3 состояния. Подумайте о состояниях, соответствующих расстоянию от цели (принимающего состояния), имеющей 2 единицы подряд. Вы начинаете далеко от этого состояния. Если вы читаете 0, вы остаетесь вдали от этого состояния. Если вы читаете 1, то вы переходите к состоянию почти там. Если вы в этом почти уверены, что происходит, когда вы читаете 0? Что происходит, когда вы читаете 1? Наконец, как только вы доберетесь туда, вы попадете в счастливое состояние, и никакие входные данные не возвратят вас в более раннее состояние.