計算理論GATE 2012

Question

4）考慮{0,1}上的字符串集合，其中3個符號的每個子字符串最多有兩個零。例如，001110和011001在語言中，但100010不是。所有長度小於3的字符串也都在語言中。下面顯示了部分完成的接受此語言的DFA。

在DFA丟失的弧是

明年我準備GATE這就是爲什麼我已經採取了GATE問題所以關於這個問題的任何幫助將是appreciated.Thank你！

Answer 1

答案是選項（D）。 首先使用不得有三個連續0的語言。所以，0輸入到00狀態必須進入死態（q），並且它只在選項（C）和（D）中定義。現在，我們只剩下兩個選項。現在你看到狀態10.在選項（C）0輸入到狀態10它只到10，它是循環和任何數字0到10它只停留在10並且10也是最終狀態，所以它是接受語言與任何沒有連續0，它不會發生。所以現在我們離開選項（D）和（D）0輸入到10它進入狀態00和一個更多的0到00它進入死狀態，因此它不會接受三個連續的0，它會做我們的語言want.and你的DFA應該這樣。

，這僅在選項（d）.sorry做了我的英語不好。