在最小的确定性有限自动机中找到状态的上限

Question

我有一个任务来确定最小确定性有限自动机器中的状态的上限，识别 language ： $ l（a_1）\ backslash l（a_2）$ ，其中 $ a_1 $ 是一个确定性有限自动机（DFA），其中 $ n $ 状态和 $ a_2 $ 是非确定性有限自动机（nfa），其中 $ M $ 状态。

我试图解决问题的方式：

1. $ l（a_1）\ setminus l（a_2）= l（a_1）\ cap l（\ sigma ^ * \ backslash l（a_2））$ ，这是一种语言，它由automaton $ l'$ 使用 $ nm $ 状态。
2. $ l'$ 的确定化，其中包含 $（nm）^ 2 $ 状态，它是状态的上限。

我是对的吗？

Answer 1

这是错误的。用 $ r $ 状态的确定可以导致dfa，最多为 $ 2 ^ r $ 状态。因此，你的论点实际上给了一个上限 $$ 2 ^ {nm}。 $$ 如果您切换操作顺序，可以改进。如果您首先将NFA转换为DFA，只需应用产品建设，那么您就会得到更好的界限 $$ n2 ^ m。 $$

此绑定对于 $ n，m $ 的无限多重值是紧密的。考虑语言 $ l_2 $ $ \ sigma ^ * \ {\ sigma_1，\ ldots，\ sigma_2 \ $ not 包含所有字母。仅使用 $ m $ 状态，有一个nfa for $ l_2 $ （具有多个初始状态）。但是， $ \ overline {l_2} $ 需要包含至少 $ 2 ^ m $ 状态。由于<跨越类=“math-container”> $ \ overline {l_2}=sigma ^ * \ setminus l_2 $ 和 $ \ sigma ^ * $ 可以通过单态DFA接受，我们看到上面的绑定是最佳的。

您可能会表明绑定是紧张的（实际上）所有 $ n，m $ 通过略微修改上面的构造，替换 $ \ sigma ^ * $ 使用 $（\ sigma ^ n）^ * $ 。