在计算如果两个任意的正则表达式有任何重叠的解决方案(假设有可能).
例如,这两个正则表达式可以显示为没有交叉的强力,因为两个解集是可计算的,因为它是有限的.
^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(11)*$} ∩ {11,^(11)*$} = {}
.....
在另一个similar question中,一个answer是计算交集正则表达式.这可以做吗？如果是这样,怎么写一个算法来做这样的事情呢？
我认为这个问题可能是halting problem的域名.
编辑：
我已经使用接受的解决方案来创建示例问题的DFA.很容易看出,如何在M_3的状态图上使用BFS或DFS来确定M_3的最终状态是否可达.
它不是停止问题的领域;决定常规语言是否为空可以解决如下：
>构建第一种语言的DFA M1.
>构建第二种语言的DFA M2.提示：Kleene的定理和功率设定机构
>构建M1相交M2的DFA M3.提示：笛卡尔产品机械施工
确定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在哪里…
> E3 = E
> Q3 = Q1×Q2(有序对)
> q0“=(q0,q0′)
> A3 = {(x,y)| A1中的x和A2中的y}
> f3(s,(x,y))=(f1(s,x),f2(s,y))
假设我没有犯错,L(M3)= L(M1)与L(M2)相交.整齐吗？
