automata - Automata - 使用 DFA 的副本构建 NFA - NFA 的正式定义

Question

我正在尝试学习如何解决以下练习。我不明白如何开始，它是压倒性的。我确实了解 DFA、NFA 以及如何将 DFA 转换为 NFA。我也理解正式的符号。

这不是家庭作业，只是为了学习。我确实有解决方案，但我也无法理解它..

如果有人可以 ELI5 练习那将是惊人的，解决此类练习的示例（有适当的解释）也会很棒，我还没有在网上找到类似的练习。

鉴于：

• 字母Σ

• 符号 c ∈ Σ

• 正则语言 L over Σ

语言 Lc = {uv | ucv ∈ L}

令 D = (Q, Σ, , q0, F) 为ℒ(D)=L 的 DFA。

展示如何使用 D 的副本构造 NFA N，使得 ℒ(N)=Lc。提供 N 的正式定义。

Answer 1

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