予想されるコイントーセスのためのDFA

Question

私はこの問題を構築しようとしています：

2つの頭が一列に現れるまでフェアコインが投げられます。コイントスの予想数は？ L + {w | wは部分文字列として11を持つ}

このDFAをマルコフチェーンとして使用して、必要な確率を計算します。 （具体的には各状態qについて、qが開始状態であればP（q）を受理状態に到達する確率とする。）

DFAを設計する際に問題があり、何か助けが必要です。

Answer 1

ヒント：

I列として11を持つすべてのバイナリ文字列から成るように言語を取ります。たとえば、01001101は言語に含まれていますが、10100010はそうではありません。ちょうど3つの状態でこれを行うことができます。状態は、2つの行を連続して持つという目標（受け入れ状態）からの距離に対応すると考えてください。あなたはその状態から遠くに出発します。 0を読んだら、あなたはその状態から遠く離れています。 1を読むと、の状態にほとんど変わりません。です。この状態になっている場合は、0を読むとどうなりますか？ 1を読むとどうなりますか？最後に - あなたがそこに着くと、あなたは幸せな状態になり、入力がなければ元の状態に戻るでしょう。