用於預期的硬幣擲幣的DFA

Question

我試圖構造這個問題：

一個公平的硬幣被拋出，直到兩個頭連續出現。擲硬幣的次數是多少？爲語言L + {w | w具有11作爲子字符串}設計DFA

使用此DFA作爲馬爾可夫鏈來計算所需的概率。 （具體來說，對於每個狀態q，如果q是開始狀態，設P（q）爲達到接受狀態的概率。）

我在設計DFA時遇到問題，需要一些幫助。

Answer 1

一個提示：

我採取由具有11作爲一個子字符串的所有二進制字符串的語言。例如，01001101在語言中，但10100010不是。你可以用3個狀態來做到這一點。將狀態視爲對應於與目標（接受狀態）之間的距離爲連續的2個狀態。你遠離那個狀態。如果您閱讀0，則遠離該狀態。如果您閱讀1，則您幾乎在處轉換到的狀態。如果您幾乎處於這種狀態 - 當您閱讀0時會發生什麼？當你閱讀1會發生什麼？最後 - 一旦你到達那裏，你處於快樂的狀態，沒有任何投入會讓你回到以前的狀態。