regular-language - 将常规语言插入其他常规语言

Question

设 L1 和 L2 是字母表 {a,b} 上的常规语言。我们定义语言 L3 如下:

L3 = {pqr | pr ∈ L1, q ∈ L2}

L3 是通过将来自L2 的字符串插入来自L1 的字符串而获得的。语言 L3 是否仍然正常？

我正在努力解决这个问题。是否可以使用字符串替换属性或正则语言的同态来证明这一点？有没有更好更简单的方法来证明这一点？

Answer 1

这里是一个结构的高级描述，表明存在接受 L3 的 NFA。

设 M1 和 M2 是最小 DFA，使得 L(M1) = L1 和 L(M2) = L2。复制 M1，因此有两个副本，M1[1] 和 M1[2]。复制 M2 所以有 |Q1|复制 M2[1]、M2[2]、…、M2[|Q1|]。此外，对状态 q1、q2、...、q|Q1| 进行编号M1的。现在为 M3 构造一个 NFA，如下所示:

1. 从 M1[1] 的状态 qk，添加一个 lambda/epsilon 转换到 M2[k] 的初始状态
2. 从 M2[k] 的接受状态，添加 lambda/epsilon 转换到 M1[2] 的状态 qk
3. 接受状态是M1[2]的接受状态
4. 初始状态为M1[1]的初始状态。

这个 NFA 读取一些输入，然后不确定地跳转到 M2 的一个实例。然后它读取 M2 中的一个字符串并跳回到它在 M1 的下一个副本中停止的地方，在那里它可以接受。该 NFA 的状态数等于 2|Q1| + |Q1| * |Q2|.