自动机-使用DFA副本构造NFA - NFA的正式定义

Question

我正在努力学习如何解决下面的练习。我不知道怎么开始，这是压倒性的。我理解DFA，NFA，以及如何将DFA转换为NFA，我也理解正式的符号。

这不是家庭作业，只是为了学习。我有办法，但我也搞不懂.

如果有人可以ELI5的练习，这将是惊人的，解决这些练习的例子(与适当的解释)也将是伟大的，我还没有找到类似的练习在网上。

给予：

• 字母表Σ
• 符号c∈Σ
• Σ上的正则语言L

语言L-c = {uv = ucv∈L}

设D= (Q，Σ，，q0，F)是ℒ(D)=L的DFA。

演示如何使用D的副本构造NFA，以便ℒ(N)=L。给出N的正式定义。

Answer 1

我不打算详细写下正式的定义。基本上你可以使用两份DFA。在第一个你开始，它没有最后的状态。对于从状态p到读取c的状态q的每一个转换，都会添加一个转换，而不是读取从第一个副本的p到第二个副本中的q的任何内容。这样你就可以跳过一个c，一旦你在第二个副本中，你就知道c已经被跳过了，如果剩下的输入导致了接受状态，你可以接受。