如何设计识别任意位置含0100101二进制串的确定性接受器

设计思路 #

采用KMP前缀匹配思路构造DFA，每个状态对应当前已经匹配到目标子串0100101的前缀长度，一旦匹配到完整子串就进入吸收型接受状态，后续任意输入都保持接受状态，保证确定性。

状态定义 #

• q0：初始状态，尚未匹配到目标子串的任何前缀
• q1：已匹配长度为1的前缀0
• q2：已匹配长度为2的前缀01
• q3：已匹配长度为3的前缀010
• q4：已匹配长度为4的前缀0100
• q5：已匹配长度为5的前缀01001
• q6：已匹配长度为6的前缀010010
• q7：接受状态，已匹配到完整子串0100101

状态转移规则 #

正确性验证 #

• 输入0100101：转移路径为q0→q1→q2→q3→q4→q5→q6→q7，最终停在接受状态，合法。
• 输入01001011：匹配到完整子串后进入q7，后续输入1仍停在q7，合法。
• 输入10100101：转移路径为q0→q0→q1→q2→q3→q4→q5→q6→q7，最终停在接受状态，合法。
• 输入010110：最长仅匹配到q2，最终停在非接受状态，拒绝，符合预期。

补充说明 #

该DFA每个状态对任意二进制输入仅有唯一转移，无歧义，且所有状态不可合并，已是最小化DFA，总状态数仅8个，运行效率最优。
内容的提问来源于stack exchange，提问作者amisotcm