用于正则表达与CFG的算法

Question

我正在寻找一种算法，该算法如果正则表达式和contex无语法的相交是空的。我知道这个问题是可以决定的，但是，我找不到任何示例实现（在伪代码中）。

如果可能的话，有人可以在.NET中为我提供这样的算法，但这不是必须的。这个问题也称为“常规交叉点”。谷歌搜索它只会给我几何算法或有关它的理论。

编辑:

任何人。我真的卡在了它上，还找不到任何东西。

Answer 1

这是我发生的方法的草图。我认为这应该起作用，但这可能不是最好的方法，因为它使用了从PDA到CFG的杂乱无章的转换。

将正则表达式转换为非确定性有限自动机（NFA），并将其降低到最小的确定有限自动机（DFA）。将无上下文的语法（CFG）转换为俯卧撑汽车（PDA）。这些第一步都是众所周知且相当简单的算法。

以DFA和PDA的交集，这也是PDA。我们会说，DFA具有状态S1，State S1，最终状态F1和表格的过渡Delta1（（（源，触发），目标），PDA和PDA具有状态S2，START State S2，最终状态F2和Transitons F2和Transitons表单的delta2（（（源，触发器，pop），（目标，按下））。新的PDA具有S1 X S2状态，每个状态都由一对标记。它具有最终状态F1 X F2，并开始状态（S1，S2）。现在进行过渡。

对于每个delta2元素的每个过渡，对于每个状态s e元素s1，找到form的delta1元素（（s，d.trigger），？）的元素。进行新的过渡（（（（（（d.source，s），d.trigger，d.pop），（（d.destination，t.destination），d.push））。

这种新的PDA应接受RE和CFG产生的语言的交集。要测试语言是否为空，您需要将其转换回CFG。算法的算法凌乱而大，但起作用。完成此操作后，标记每个终端符号。然后标记每个具有一个规则的符号，其中右侧只有标记符号，然后重复直到您不再标记更多符号为止。如果您可以标记开始符号，则语言不是空的。否则，语言为空。