DFA 中接受具有“1”作为右起第 5 个符号的字符串所需的最少状态数是多少?字符串在字母表 {0,1} 上定义。
问问题
3517 次
1 回答
2
Myhill-Nerode 定理是解决这类问题的有用工具 。
这个想法是建立一组字符串的等价类,使用“区分扩展”的想法。考虑两个字符串 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 被接受。这给出了 2 5 = 32 个等价类。
如果 s 是长度为 k < 5 个字符的字符串,则它与 0 (5-k) s属于相同的等价类(即在左侧添加 0-padding 直到它的长度为 5 个字符)。
如果 s 是长度为 k > 5 个字符的字符串,则其等价类由其最后 5 个字符确定。
因此,{0,1} 上的所有字符串都属于上述 32 个等价类之一,并且根据 Myhill-Nerode 定理,该语言的最小 DFA 具有 32 个状态。
于 2011-12-04T09:07:45.960 回答