用cfg求正则表达式交的算法

Question

我正在寻找一种算法，如果正则表达式和contex空闲文法的交集是否为空，则该算法将输出。我知道这个问题是可以确定的，但是，我找不到任何示例实现(用伪代码)。

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

编辑

任何人。我真的被困在上面了，还找不到任何东西。

Answer 1

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

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

取DFA与PDA的交汇处，这也是PDA。我们将说DFA具有表单的状态s1、启动状态S1、最终状态F1和转换状态delta1 ((源、触发器)、目的地)，并且PDA具有窗体的状态S2、启动状态s2、最终状态F2和过渡状态delta2 ((源、触发器、pop)、(目的地、推送))。新的PDA有状态S1 X S2，每个状态由一对标记。它有最终状态F1 X F2和启动状态(s1，s2)。现在是过渡阶段。

对于每个转换d( delta2的一个元素)，对于每个状态的元素( s1 )，查找形式((s，d.trigger)，?)的delta1元素的转换t。进行新的转换(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年。简单短语结构语法的形式性质中校Phonetik，Sprachwissen科姆。15 (I961)，143-172。Y.Bar-Hillel，“语言与信息”，艾迪生-韦斯利，雷丁，马萨诸塞州(1965年)，116-150.

但是，您可以在以下内容中找到一个更简单的版本：

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

如果有帮助的话，这个解决方案是用Pyformlang (https://pyformlang.readthedocs.io/)实现的，您可以在Github (https://github.com/Aunsiels/pyformlang/blob/master/pyformlang/cfg/cfg.py)上找到它。