如何表明如果语言L是规则的，那么L'是正则的？

Question

设L是任何正则语言和∈Σ。如何显示语言L'= {uav | uv∈L}也是正常的吗？

维基百科说，一种方法来证明它是把它引回到正规语言，但我不明白在这种情况下如何做到这一点。希望有人能帮助。

Answer 1

有很多方法可以显示出来。我认为构建DFA的论点特别容易可视化。

想象一下您的语言L的DFA。我们称之为M。想象一下，它在图表上以图表形式展开。现在，想象一下M的副本，并将其在M旁边展开。叫它M'。

现在 - 从M，从国家的Mq添加一个新的过渡到相应状态的M'q'。过渡是符号a。

现在，考虑启动状态为M的开始状态和接受状态为M'的接受状态的集合机器。本机开始接受L中的字符串，然后接受中间某个地方的a，然后继续从L中断处继续接受字符串。这是我们要去的语言，我们为它定义了一个完全合理的NFA。由于NFA接受的任何语言都是正常的，我们的语言是正常的。