1

让语言 L_n 具有字符集 Sigma = {a_1, ..., a_n}。L_n 恰好有那些包含某些字符奇数次的单词。等效地，如果 L_n^i 是每个单词包含奇数个 a_i 的语言，则 L_n = L_n^1 union ...union L_n^n。

我已经生成了一个接受 L_n 的 NFA 和一个 2^n 状态的 DFA，它也可以。

我现在需要证明这是接受这种语言的最小 DFA。我得到提示，假设有一个接受 L_n 的 k < 2^n 个状态的 DFA，然后表明Sigma^* 中有一些字符串u,v ，其中u包含a和奇数次，v包含它是偶数次，并且 DFA 必须在同一状态下终止。

我一直试图将 2^n 作为一个强有力的提示，比如可能考虑所有长度为 n 的字符串，但其中有 n^n 个。也许考虑所有长度为 n 的字符串只使用字符a,b。由于有 k < 2^n 个状态，因此必须将一些像这样的两个字符串发送到相同的状态。这组中被拒绝的字符串是具有偶数a和b的字符串，但我无法知道这些实例的两个这样的实例是否进入相同的状态，或者如果它们确实如此，那会有什么关系。

也许考虑所有字符串的选择，其中 a_1 出现一次或 0 次， a_2 出现一次或 0 次，等等。这些有 2^n 选择，因此其中一些必须进入相同状态。唯一不在该语言中的字符串是空字符串。我还是被困住了。

4

2 回答 2

1

每个 a_i 在任何给定的输入字符串中出现奇数次或偶数次。对于任何给定的字符串，都有一个最短的字符串，其符号按字典顺序排列，如果将其附加到给定的字符串上，则会导致字符串不在该语言中。该字符串将最多有一个字母符号，按索引顺序排列，以使所有符号的奇偶性计数均匀。

这意味着 2^n 奇偶校验配置中的每一个都可以根据 Myhill-Nerode 不可区分关系进行区分；该语言有 2^n 个类，因此最小 DFA 必须具有 2^n 个状态。

我认为这基本上就是您的直觉，只是为了明确使用 Myhill-Nerode 和不可区分的关系而重述。

编辑：添加一个示例以使其更清晰。

考虑字母表{a, b, c}。然后在任何字符串中，a、b 和 c 中的每一个都出现偶数次或奇数次。考虑 2^3 = 8 个最短字符串，其符号按字典顺序排列，涵盖所有可能的情况：

  1. e：所有字符串出现偶数次
  2. a：a出现奇数次，b和c出现偶数次
  3. b：与a相同，但b
  4. c: 与 a 和 b 相同，但 c
  5. ab：a和b出现奇数次，c出现偶数次
  6. ac：与ab相同，但ac
  7. bc：与 ab 和 ac 相同，但 bc
  8. abc：a、b 和 c 都出现奇数次

对于覆盖所有奇偶校验配置的这些最短字符串中的每一个，都有一个对应的最短字符串，其中符号按字典顺序排序，这导致串联具有偶数个所有符号。片刻思考表明，这样的最短字符串与表示该类的最短字符串相同：对于上述 8 个最短代表中的每一个，与自身连接会产生一个字符串，其所有符号出现的次数为偶数，并且不可能有短字符串产生相同的效果。

  1. ee = e
  2. aa = aa
  3. bb = bb
  4. cc = cc
  5. ab.ab = abab
  6. ac.ac = acac
  7. bc.bc = bcbc
  8. abc.abc = abcabc

就 Myhill-Nerode 而言，等价类 [x] 必须与等价类 [y] 不同，因为可以跟随 [x] 中的字符串并且不会导致 L 中的字符串的最短字符串是 x，而最短的可以跟在 [y] 中的一个字符串之后并且不会导致 L 中的一个字符串的字符串是 y，并且我们已经要求 x 和 y 不同。我们可以确认我们的 8 个案例：

  1. ea, eb, ec, e.ab., e.ac, e.bc, e.abc 各有至少一个符号出现奇数次 (a, b, c, a, a, b, a)
  2. ae、ab、ac、a.ab、a.ac、a.bc、a.abc 各有至少一个符号出现奇数次（a、a、a、b、c、a、b）
  3. be、ba、bc、b.ab、b.ac、b.bc、b.abc 各有至少一个符号出现奇数次（b、a、b、a、a、c、a）
  4. ce、ca、cb、c.ab、c.ac、c.bc、c.abc 各有至少一个符号出现奇数次（c、a、b、a、a、b、a）
  5. ab.e、ab.a、ab.b、ab.c、ab.ac、ab.bc、ab.abc 各有至少一个符号出现奇数次（a、b、a、a、b、一，三）
  6. ac.e, ac.a, ac.b, ac.c, ac.ab, ac.bc, ac.abc 各有至少一个符号出现奇数次 (a, c, a, a, b,一，乙）
  7. bc.e、bc.a、bc.b、bc.c、bc.ab、bc.ac、bc.abc 各有至少一个符号出现奇数次（b、a、c、b、a、一，一）
  8. abc.e、abc.a、abc.b、abc.c、abc.ab、abc.ac、abc.bc 各有至少一个符号出现奇数次（a、b、a、a、c、乙，甲）
于 2017-09-25T20:59:56.623 回答
0

您对字符串“a_1 出现一次或 0 次...”的想法很好。但是将它们视为字符串的末端，如下所示：

假设您已经读取了一个输入字符串并且处于状态 q。

  1. 假设输入字符串的所有符号为偶数。那么所有至少有一个符号的延续（出现一次，因此出现奇数）应该导致接受，其他的（这里只有空字符串）不会。
  2. 假设输入字符串除了 a_1 之外的所有符号都是偶数。那么所有不包含 a_1 或包含 a_1 并且至少有一个除 a_1 以外的符号的延续都应该导致接受，其他的则不会。
  3. ...

您恰好遇到了 2^n 种不同的情况和不同的字符串集，它们应该会导致接受/拒绝。因此，状态 q 在每种情况下都必须不同，因此必须至少有 2^n 个。

于 2017-09-25T10:05:36.297 回答