计算两个无限正则表集解决方案集是否相交

Question

在计算两个任意正则表达式是否有任何重叠的解决方案(假设它是可能的).

例如,这两个正则表达式可以通过强力显示没有交叉点,因为这两个解决方案集是可计算的,因为它是有限的.

^1(11){0,1000}$ ?     ^(11){0,1000}$        = {}
{1,111, ..., ..111} ? {11,1111, ..., ...11} = {}
{}                                          = {}

但用{0,1000}通过*删除一个蛮力解决方案的可能性,所以一个更聪明的算法必须创建.

^1(11)*$ ? ^(11)*$ = {}
{1,^1(11)*$} ? {^(11)*$} = {}
{1,^1(11)*$} ? {11,^11(11)*$} = {}
{1,111,^111(11)*$} ? {11,^(11)*$} = {}
.....

在另一个类似的问题中,一个答案是计算交集正则表达式.这可能吗？如果是这样,怎么会写一个算法来做这样的事情？

我认为这个问题可能是暂停问题的结果.

编辑:

我已经使用已接受的解决方案为示例问题创建了DFA.可以很容易地看到如何在状态图上使用BFS或DFS M_3来确定是否可以达到最终状态M_3.

Answer 1

它不在停止问题的范围内; 判断常规语言的交集是否为空可以解决如下:

1. 为第一语言构建DFA M1.
2. 为第二语言构建DFA M2.提示:Kleene的定理和动力装置机器结构
3. 为M1相交M2构造DFA M3.提示:笛卡尔产品机器结构
4. 确定L(M3)是否为空.提示:如果M3有n个状态,并且M3不接受任何长度不大于n的字符串,则L(M3)为空......为什么？

这些事物中的每一个都可以通过算法完成和/或检查.此外,当然,一旦您有DFA识别您的语言的交集,您就可以构建一个与该语言匹配的正则表达式.如果你从正则表达式开始,你可以制作DFA.这绝对是可计算的.

编辑:

因此,要构建笛卡尔积分机,您需要两个DFA.设M1 =(E,q0,Q1,A1,f1),M2 =(E,q0',Q2,A2,f2).在两种情况下,E是输入字母,q0是开始状态,Q是所有状态的集合,A是接受状态的集合,f是转换函数.构建M3 ......

1. E3 = E.
2. Q3 = Q1 x Q2(有序对)
3. q0''=(q0,q0')
4. A3 = {(x,y)| A1中的x和A2中的y}
5. f3(s,(x,y))=(f1(s,x),f2(s,y))

如果我没有犯任何错误,则L(M3)= L(M1)与L(M2)相交.整洁,对吧？