finite-automata - 对于给定的正确输入字符串，如何纠正稍微不正确的 DFA？

Question

我写了一个可以生成 DFA 的程序。但是 DFA 有点不正确。也就是说，有时他们不能接受正确的字符串。

我的问题是：是否有任何算法可以纠正 DFA，以便它们可以接受给定的正确字符串？

更正式地说，

假设 DFA D不接受字符串str。

需要一个算法A , st D' = A( D, str)并且D'接受str

Answer 1

您可以将要接受的附加字符串表示为链自动机，然后简单地将这些链与 DFA D 合并。之后，您可能还需要确定联合机器。