插入下的常规语言闭包

Question

假设我在字母表 Σ 下有一个常规语言 L。中间插入一个符号，如何证明语言L'仍然是常规语言？

例如，L 包含一个字符串 w，它由两个子字符串 u 和 v (w = uv) 组成 我想证明常规语言 L' 包含一个字符串 uxv，其中 x 是插入的符号。

请注意，u 和 v 不必具有相同的长度，并且 x 也在相同的字母表 Σ 中。

谢谢！

Answer 1

因为L是正则的，所以存在接受它的有穷自动机A。制作 A 的两个副本（A1 和 A2）。在 A2 中，使开始状态不是初始状态。对于 A1 中的每个状态 p，添加一个转换 p --x--> p 到 A2 中的相应状态。

使用您示例的符号，现在 A1 读作 u，新转换读作 x，A2 读作 v。