插入正规语言

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。