PDA和正则表达式

Question

我有一个PDA和一些正则表达式。是否有任何算法可用于确保我的PDA接受的字符串是正则表达式可以生成的子集？

谢谢！

吉尔

Answer 1

听起来你问这个：给定一个PDA M和一个正则表达式r，产生一个接受语言L（M）与L（r）相交的PDA。如果这是你想要的，那么答案是肯定的，而且结构繁琐但直截了当：

1. 使用一些结构将正则表达式r转换为NFA N，例如，在正则表达式和有限自动机的等价性的建设性证明中使用的结构
2. 确定NFA N以使用某种结构来获得DFA M'，例如，powerset（或子集）结构，或任何用于非确定性和确定性FAs等价性的建设性证据中使用的结构
3. 可选地，使用一些DFA最小化算法最小化M'以获得M''
4. 现在，构建新的PDA P如下： 状态将是所有有序对（a，b），其中a是PDA M中的状态，b是DFA M'中的状态 每当转换到PDA M中的'on s'和转换为DFA M'中的s'时，转换将从符号s上的状态（a，b）到（a'，b'）（对于epsilon-过渡，从（a，b）到（a'，b））。 初始状态（ai，bi）将分别由PDA M和DFA M''的初始状态ai和bi组成。 接受状态将是两个组件在其各自的机器中接受的状态（成对（a，b），其中a接受PDA M且b接受DFA M''） 根据PDA M的转换更新堆栈

如此构造的机器将接受PDA M接受并与正则表达式r匹配的所有内容。