我在寻找一个算法，如果一个正则表达式和一个上下文无关语法的交集是空的或不是。我知道这个问题是可以判定的，但是，我找不到任何示例实现（在伪代码中）。
如果可能的话，可以有人在.net中为我提供这样的算法，但这不是必须的。这个问题也被称为“正交集”谷歌搜索只给了我几何算法或理论。
编辑：
任何人我真的很纠结，什么也找不到。
最佳答案
这是我想到的一个方法的草图。我认为这应该是可行的，但这可能不是最好的方法，因为它使用了从PDA到CFG的非常混乱的转换。
将正则表达式转换为不确定有限自动机（NFA），并将其降为最小确定有限自动机（DFA）将上下文无关语法（CFG）转换为下推automoton（PDA）这些第一步都是众所周知的并且相当简单的算法。
以dfa和pda的交叉点为例，pda也是pda。我们会说，DFA有状态S1、开始状态S1、最终状态F1和表单的转换delta1（（source，trigger），destination），PDA有状态S2、开始状态S2、最终状态F2和表单的转换delta2（（source，trigger，pop），（destination，push））新的pda有状态s1 x s2，每个状态由一对标记。它有最终状态f1 x f2和开始状态（s1，s2）。现在开始过渡。
对于每个转换d delta2的一个元素，对于每个状态s一个元素s1，找到该形式的delta1的转换t一个元素（（s，d.trigger），？）。进行新的转换（（（d.source，s），d.trigger，d.pop），（（d.destination，t.destination），d.push）。
这个新的PDA应该接受RE和CFG生成的语言的交集要测试语言是否为空，需要将其转换回CFG这方面的算法杂乱无章，而且很大，但它是有效的。完成后，标记每个端子符号。然后标记每一个有规则的符号，其中只有标记的符号在右手边，并重复，直到您不能标记更多的符号。如果可以标记开始符号，则语言不是空的否则，语言是空的。