最小化具有不关心过渡的 DFA

Question

我有一个dfa( q ，＆sigma; ,, ＆delta; ， q q ₀， f (带有一些"不在乎过渡"。这些过渡模型符号已知在某些情况下未出现在输入中。如果进行了任何此类过渡，那么结果字符串是否被接受都无关紧要。

是否有算法来计算具有最少状态的等效DFA？正常的DFA最小化算法无法使用，因为他们不知道"不在乎"过渡，并且似乎没有一种显而易见的方法来扩展算法。

Answer 1

我认为这个问题是np-hard(稍后详细介绍(。这是我尝试的。

1. (可选(通过接受/拒绝/不关心单独结果的通常最小化算法进行预处理。(由于不在乎不相同接受或拒绝，我们会得到myhill -nerode等价关系，允许使用通常的算法的变体。(

2. 生成冲突图如下所示。从接受和拒绝国家之间的所有边缘开始。进行闭合，我们迭代添加边缘q ₁ - q 2 ，以便存在一个符号s，那里存在边缘＆sigma;(q 1 ，s( - ＆sigma;(q ₂ ，s(。

3. 将此图颜色尽可能少。(或大约(。那里有很多着色算法。partialcol是一个很好的起点。

4. 将每个颜色类合并为一个节点。这有可能使新的过渡函数多价值，但我们可以任意选择。

访问任意尺寸的字母，似乎很容易使这种降低到以相反的方式运行，从而证明了NP硬度。对我来说，开放的问题是，拥有固定尺寸的字母是否以使所产生的着色实例更容易的方式约束冲突图。las，我没有时间研究这个。

Answer 2

我相信普通摩尔算法的略有变化。这是算法的陈述。

Let S be the set of states.
Let P be the set of all unordered pairs drawn from S.
Let M be a subset of P of "marked" pairs.
Initially set M to all pairs where one state is accepting and the other isn't. 
Let T(x, c) be the transition function from state x on character c.
Do
  For each pair z = <a, b> in P - M
    For each character c in the alphabet
      If <T(a, c), T(b, c)> is in M
        Add z to M and continue with the next z
Until no new additions to M

最终集p -m是状态上等价关系的成对描述。您可以通过合并原始状态和过渡来创建最低DFA。

我相信，不关心过渡可以通过永远不会基于它们对(添加到M(对来处理过渡。也就是说，我们更改一行：

      If T(a, c) != DC and T(b, c) != DC and <T(a, c), T(b, c)> is in M   

(实际上，在实施中，如果DC是类型状态的保留值，而不是原始FA中的状态。(

。(

我现在没有时间考虑正式的证据，但这对我来说是直觉的。我们基于我们知道永远不会发生的过渡，跳过状态的等效类别。

我仍然需要向我自己证明的是，集合P -M是否仍然是对等效关系的成对描述。即，我们可以最终使用<a,b>和<b,c>而不是<a,c>？如果是这样，是否有修复程序？