dfa - 用于 Kleene 星操作的 DFA

Question

对于语言 L*，DFA 拥有的最多状态数是多少？是否可以在这里定义最坏的情况？

Answer 1

正如 Welbog 指出的，L* 可以有任意数量的状态。虽然这并不一定很明显，所以我们不妨尝试证明它。证明很简单：我们将描述一系列正则语言，使得第 N 种语言的 DFA 中的最小状态数等于 N。

我们的常规语言将是 {a}, {aa}, {aaa}, ...，即由从语言 a* 中提取的单个非空字符串组成的有限常规语言序列，按长度升序排列.

语言 {a}* 的最小 DFA 有一个状态（假设字母表 {a}）在 a 上循环到自身。

语言 {aa}* 的最小 DFA 有两种状态：初始状态仍在接受，但我们需要一个非接受状态来接受具有多个 a 不能被 2 整除的字符串。

一般来说，语言 {a^n}* 的最小 DFA 有 n 个状态：初始状态仍然是接受状态，但我们需要 n-1 个非接受状态来跟踪 |w| 的值。% n。我们必须跟踪这个值，以便我们可以知道我们是否看到了许多可以被 n 整除的 a，并且在 DFA 中，跟踪到目前为止看到的 a 数量的唯一方法是更改​​为新的独特状态。

这个建设性的证明使我们能够提供证据证明 L* 的最小 DFA 的大小没有上限：如果 m 个状态存在这样的限制，我们只需指出语言 (a^(m+ 1))* 必须有更大的 DFA。