忽略过渡而最小化DFA

Question

我有一个DFA（Q，Σ，δ，q ₀，F），带有一些“无关转换”。这些转换模拟了某些情况下不会出现在输入中的符号。如果进行了任何这样的转换，则结果字符串是否被接受都无关紧要。

是否有一种算法可以计算最少状态的等效DFA？无法使用普通的DFA最小化算法，因为它们不了解“无关”转换，并且似乎没有明显的方法可以扩展算法。

Answer 1

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

1. （可选）通过通常的最小化算法对输入进行预处理，将接受/拒绝/不关心作为单独的结果。（因为 don't care 不等于接受或拒绝，我们得到 Myhill-Nerode 等价关系，允许通常算法的变体。）

2. 生成冲突图如下。从接受和拒绝状态之间的所有边缘开始。取闭包，我们迭代地添加边 q ₁ —q ₂使得存在一个符号 s，其中存在一条边 σ(q ₁ , s)—σ(q ₂ , s)。

3. 用尽可能少的颜色为该图着色。（或近似值。）有很多着色算法。PartialCol 是一个很好的起点。

4. 将每个颜色类合并到一个节点中。这可能使新的转移函数具有多值性，但我们可以任意选择。

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