用字母 { a }定义语言L如下
L = { 一个nk | k > 0 ; n 是一个正整数常数 }
DFA 中识别L所需的状态数是多少?
在我看来它应该是 k+1 但我不确定。
用字母 { a }定义语言L如下
L = { 一个nk | k > 0 ; n 是一个正整数常数 }
DFA 中识别L所需的状态数是多少?
在我看来它应该是 k+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 n时遇到的状态序列 S 0、S 1、... S n。S n必须是一个接受状态,因为一个n在 L 中。但是由于这个 DFA 中的不同状态少于 n+1 个,根据鸽巢原理,一定有某个状态至少被访问过两次。删除该循环会给出另一个路径(和另一个接受的字符串),长度 < n,从 S 0到 S n。但是 L 不包含比 n 短的字符串,这与我们的假设相矛盾。因此,没有少于 n+1 个状态的 DFA 可以识别 L。