使用无关转换最小化 DFA

Question

我有一个 DFA (Q, Σ, δ, q₀, F) 和一些“无关转换”。这些转换模型符号已知在某些情况下不会出现在输入中。如果采取任何此类转换，则结果字符串是否被接受都无关紧要。

有没有一种算法可以用最少的状态来计算等效的 DFA？不能使用普通的 DFA 最小化算法，因为它们不知道“不关心”转换，而且似乎没有明显的方法来扩展算法。

Answer 1

我相信对正常的摩尔算法稍加改动就可以了。这是算法的声明。

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> 结束？如果是这样，是否有修复？

Answer 2

我认为这个问题是 NP-hard（稍后会详细介绍）。这就是我要尝试的。

（可选）通过通常的最小化算法预处理输入，accept/reject/don不关心作为单独的结果。（因为不关心不等同于接受或拒绝，我们得到 Myhill–Nerode 等价关系，允许通常算法的变体。）
生成冲突图如下。从接受和拒绝状态之间的所有边缘开始。以我们迭代添加边 q₁—q₂ 的闭包为例，这样就存在一个符号 s，其中存在一条边 σ(q₁, s)—σ(q₂, s).
用尽可能少的颜色给这张图上色。（或近似值。）那里有很多着色算法。 PartialCol 是一个很好的起点。
将每种颜色 class 合并到一个节点中。这潜在地使新的转换函数multi-valued，但我们可以任意选择。

通过访问任意大小的字母表，似乎很容易以另一种方式减少着色运行，证明 NP-hardness。对我来说，悬而未决的问题是 fixed-size 字母表是否会以某种方式限制冲突图，从而以某种方式使生成的着色实例更容易。唉，没时间研究这个

使用无关转换最小化 DFA

Minimize a DFA with don't care transitions

language-agnostic

algorithm

dfa