我试图以多种方式解决这个问题，并在几个地方都没有答案。问题如下：
[问题]
给定两种常规语言（可以称为有限描述语言，idk）L1和L2，我们定义一种新语言如下：
L = {w1w2| there are two words, x,y such that : xw1 is in L1, w2y is in L2}
我应该用来证明L is regular，但是我有以下限制：
我必须使用 Equivalence 类，别无他法
我不能使用Rank(L)，如显示对等价类数量的限制，而是必须显示它们
我并不期待一个完整的证明（尽管这将不胜感激），而是对如何去做这样的事情的解释。
提前致谢。
L = {w1w2| 有两个单词 x,y 使得： xw1 在 L1 中，w2y 在 L2 中} 如果 L 1和 L 2是正则语言，则它是正则的。
L suff = { w 1 | xw 1 ∈ L 1 }
L pref = { w 2 | w 2 y ∈ L 2 }
和，
L = L suff L pref
我们可以很容易地通过构造有限自动机来证明L.
假设 L 1的有限自动机(FA)是 M 1并且 L 2的 FA是 M 2。
[解决方案]
L 的非确定性有限自动机（NFA）可以通过从 M 1中的每个状态到 M 2中的每个状态引入 NULL 转换（^-edge）来绘制。然后NFA可以转换为DFA。
例如
L 1 = {ab ,ac} 和 L 2 = {12, 13}
L = {ab, ac, 12, 13, a12, a2, ab12, ab2, a13, a3, ab13, ab3, ....}
注意： w 1和 w 2 可以为 NULL
M 1 = 由 Q = {q 0 ,q 1 ,q f } 和边组成：
q 0 ---a----->q 1 ,
q 1 ---b/c--->q f
相似地 ：
M 2 = 由 Q = {p 0 ,p 1 ,p f } 和边组成：
p 0 ---1----->p 1 ,
p 1 ---2/3--->p f
现在，称为 M 的 L 的 NFA 将由 Q = {q 0 ,q 1 ,q f , p 0 ,p 1 ,p f } 组成，其中 M 的最终状态是 p f并且边是：
q 0 ---a----->q 1 ,
q 1 ---b/c--->q f ,
p 0 ---1----->p 1 ,
p 1 --- 2/3--->p f ,q 0 ----^----> p 0 ,
q 1 ----^----> p 0 ,
q f ----^----> p 0 ,q 0 ----^----> p 1 ,
q 1 ----^----> p 1 ,
q f ----^----> p 1 ,q 0 ----^----> p f ,
q 1 ----^----> p f ,
q f ----^----> p f
^表示 NULL 转换。
现在，一个 NFA 可以很容易地转换为 DFA。（我留给你）
[ANSWER]
L 的 DFA 是可能的，因此 L 是正则语言。
我强烈鼓励你画出 DFA/NFA 的图，这样概念就清楚了。>