algorithm - 正则表达式与cfg相交的算法

Question

我正在寻找一种算法，如果正则表达式和上下文无关语法的交集为空，则输出该算法。我知道这个问题是可判定的，但是，我找不到任何示例实现（在伪代码中）。

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

编辑：

任何人。我真的坚持下去，还找不到任何东西。

Answer 1

这是我想到的一种方法的草图。我认为这应该可行，但它可能不是最好的方法，因为它使用了从 PDA 到 CFG 的非常混乱的转换。

将正则表达式转换为非确定性有限自动机 (NFA)，并将其简化为最小确定性有限自动机 (DFA)。将上下文无关文法 (CFG) 转换为下推自动机 (PDA)。这些第一步都是众所周知且相当简单的算法。

以 DFA 和 PDA 的交集为例，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，找到转换 t 是 delta1 的一个元素，形式为 ((s,d.trigger),?)。进行新的过渡（（（d.source，s），d.trigger，d.pop），（（d.destination，t.destination），d.push））。

这个新的 PDA 应该接受 RE 和 CFG 产生的语言的交集。要测试语言是否为空，您需要将其转换回 CFG。该算法既混乱又庞大，但它确实有效。完成后，标记每个终端符号。然后标记每个符号的规则，即右侧只有标记的符号，并重复，直到你不能标记更多的符号。如果可以标记开始符号，则语言不为空。否则，语言为空。

Answer 2

事实上，有一种更简单的算法可以计算上下文无关文法和正则表达式之间的交集。它不使用下推自动机，通过多次转换从 CFG 获得可能会很昂贵。

该解决方案出现在：

Y. Ba-Hillel、M. Prles 和 E. Shamir。1965.关于简单短语结构语法的形式属性。Z.Phonetik，Sprachwissen。康姆。15 (I961), 143-172。Y. Bar-Hillel，语言和信息，Addison-Wesley，阅读，马萨诸塞州（1965 年），116-150。

但您可以在以下位置找到更简单的版本：

理查德·贝格尔和威廉·加萨奇。.. 一个证明上下文无关语言和常规语言的交集是上下文无关的，它不使用下推自动机。 http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf (.)。

如果有帮助，这个解决方案是在 Pyformlang ( https://pyformlang.readthedocs.io/ ) 中实现的，你可以在 Github for Python ( https://github.com/Aunsiels/pyformlang/blob/master/pyformlang /cfg/cfg.py )