Hen*_*nri 2 algorithm grammar language-theory
我正在寻找一种算法，该算法可以输出正则表达式和上下文无关文法的交集是否为空。我知道这个问题是可判定的，但是，我找不到任何示例实现（在伪代码中）。
如果可能的话，有人可以在 .NET 中为我提供这样的算法，但这不是必须的。这个问题也被称为“规则交集”。谷歌搜索只给了我几何算法或关于它的理论。
编辑：
任何人。我真的坚持下去了，还没有找到任何东西。
这是我想到的一种方法的草图。我认为这应该可行，但它可能不是最好的方法，因为它使用了从 PDA 到 CFG 的非常混乱的转换。
将正则表达式转换为非确定性有限自动机 (NFA)，并将其简化为最小确定性有限自动机 (DFA)。将上下文无关文法 (CFG) 转换为下推自动机 (PDA)。这些第一步都是众所周知且相当简单的算法。
拿 DFA 和 PDA 的交集来说，它也是一个 PDA。我们会说 DFA 有状态 S1、开始状态 s1、最终状态 F1 和形式 ((source,trigger),destination) 的转换 delta1，而 PDA 有状态 S2、开始状态 s2、最终状态 F2 和转换形式为 ((source,trigger,pop),(destination,push)) 的 delta2。新的 PDA 有状态 S1 X S2，每个状态用一对标记。它具有最终状态 F1 X F2 和开始状态 (s1,s2)。现在是过渡。
对于每个转换 d 是 delta2 的一个元素，对于每个状态 s 是一个元素 s1，找到形式为 ((s,d.trigger),?) 的转换 t 是 delta1 的元素。进行新的转换 (((d.source, s), d.trigger, d.pop),((d.destination, t.destination),d.push))。
这个新的 PDA 应该接受 RE 和 CFG 产生的语言的交集。要测试语言是否为空，您需要将其转换回 CFG。该算法是混乱和庞大的，但它的工作原理。完成后，标记每个终端符号。然后标记每个具有规则的符号，其中右侧只有标记的符号，并重复直到您无法标记更多符号。如果可以标记开始符号，则语言不为空。否则，语言是空的。