如何证明如果语言 L 是正则的，那么 L' 是正则的？
How to show that if the language L is regular, then L' is regular?
令L为任何正则语言且a∈Σ。如何证明语言 L'={uav | uv ∈ L}也是正则的？
维基百科说证明它的一种方法是将其引导回常规语言，但我不明白在这种情况下该怎么做。希望有人能帮忙。
有很多方法可以证明这一点。我认为我们构建 DFA 的论点特别容易形象化。
为您的语言 L 想象一个 DFA。我们称它为 M。想象一下它在 table 上以图表形式展开。现在，想象一下制作 M 的副本并将其散布到 table 上的 M 旁边。称之为 M'.
现在 - 从 M，添加从 M 的状态 q 到 M' 的相应状态 q' 的新转换。转换在符号 a.
上
现在考虑聚合机，其起始状态为M的起始状态，其接受状态为M'的接受状态。这台机器开始接受 L 中的字符串，然后在中间某处接受 a 中的字符串，然后从它停止的地方继续接受 L 中的字符串。这就是我们想要的语言，我们已经为它定义了一个完全合理的 NFA。由于 NFA 接受的任何语言都是正则的，因此我们的语言也是正则的。
令L为任何正则语言且a∈Σ。如何证明语言 L'={uav | uv ∈ L}也是正则的？
维基百科说证明它的一种方法是将其引导回常规语言，但我不明白在这种情况下该怎么做。希望有人能帮忙。
有很多方法可以证明这一点。我认为我们构建 DFA 的论点特别容易形象化。
为您的语言 L 想象一个 DFA。我们称它为 M。想象一下它在 table 上以图表形式展开。现在，想象一下制作 M 的副本并将其散布到 table 上的 M 旁边。称之为 M'.
现在 - 从 M，添加从 M 的状态 q 到 M' 的相应状态 q' 的新转换。转换在符号 a.
现在考虑聚合机，其起始状态为M的起始状态，其接受状态为M'的接受状态。这台机器开始接受 L 中的字符串，然后在中间某处接受 a 中的字符串，然后从它停止的地方继续接受 L 中的字符串。这就是我们想要的语言，我们已经为它定义了一个完全合理的 NFA。由于 NFA 接受的任何语言都是正则的，因此我们的语言也是正则的。