finite-automata - DFA 中从右数第 5 个符号为“1”的最小状态数

Question

DFA 中接受具有“1”作为右起第 5 个符号的字符串所需的最少状态数是多少？字符串在字母表 {0,1} 上定义。

Answer 1

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 ⁵ = 32 个等价类。

^{如果 s 是长度为 k < 5 个字符的字符串，则它与 0 (5-k)} s属于相同的等价类（即在左侧添加 0-padding 直到它的长度为 5 个字符）。

如果 s 是长度为 k > 5 个字符的字符串，则其等价类由其最后 5 个字符确定。

因此，{0,1} 上的所有字符串都属于上述 32 个等价类之一，并且根据 Myhill-Nerode 定理，该语言的最小 DFA 具有 32 个状态。