DFA中具有'1'作爲第5個符號的狀態的最小數量

Question

DFA接受右側具有'1'作爲第5個符號的字符串所需的狀態的最小數量是多少？字符串定義在字母{0,1}上。

Answer 1

Myhill-Nerode theorem是解決這些問題的有用工具。

這個想法是建立一組等價類的字符串，使用「區分擴展」的想法。考慮兩個字符串x和y。如果存在一個字符串z ，使得xz和yz中的一個在語言中，那麼z是一個可區分的擴展， 並且x和y必須屬於不同的等價類。每個等價類都映射到最小DFA中的不同狀態。

對於您描述的語言，讓x和y爲{0,1}上的任何一對不同的5個字符的字符串 。如果它們在位置n（從右開始，從1開始）不同，那麼長度爲5-n的任何字符串z將是一個可區分的擴展：如果x在位置n處具有0，則 且y在位置n處具有1 ，那麼xz被拒絕並且yz被接受。這給出了等價類。

如果s是與長度爲k < 5個字符的字符串，它屬於同一個等價類 爲0 ^（5-k）個 S（即填充0添加到左側，直到它的5個字符長）。

如果s是長度爲k> 5個字符的字符串，則其等價類由其最後5個字符確定。

因此，{0,1}上的所有字符串都屬於上述32個等價類之一，並且通過Myhill-Nerode定理，此語言的最小DFA有32個狀態。