finite-automata - 需要的最少状态数？

Question

用字母 { a }定义语言L如下

L = { 一个^nk | k > 0 ; n 是一个正整数常数 }

DFA 中识别L所需的状态数是多少？

---

在我看来它应该是 k+1 但我不确定。

Answer 1

语言 L 可以被具有 n+1 个状态的 DFA 识别。

观察 L 中任何字符串的长度都等于 0 mod n。

用整数 0, 1, 2, ... n-1 标记 n 个状态，表示每个可能的余数。附加状态 S 是起始状态。S 有一个单一的转换，到状态 1。如果机器当前处于状态 i，则在输入时它移动到状态 (i+1) mod n。状态 0 是唯一的接受状态。（如果空字符串是 L 的一部分，我们可以消除 S 并使状态 0 成为开始状态）。

假设有一个具有少于 n+​​1 个状态的 DFA 仍然可以识别 L。考虑在处理字符串a ⁿ时遇到的状态序列 S ₀、S ₁、... S _n。S _n必须是一个接受状态，因为一个ⁿ在 L 中。但是由于这个 DFA 中的不同状态少于 n+​​1 个，根据鸽巢原理，一定有某个状态至少被访问过两次。删除该循环会给出另一个路径（和另一个接受的字符串），长度 < n，从 S ₀到 S _n。但是 L 不包含比 n 短的字符串，这与我们的假设相矛盾。因此，没有少于 n+​​1 个状态的 DFA 可以识别 L。