如何将cfg转换为具有2种状态的pda？

Question

我在计算机科学理论的研究中遇到了一些问题......

任何人都可以向我解释一下如何将上下文无关语法（cfg）转换为相应的下推自动机（pda）的算法吗？ 只有 2 个状态？

Answer 1

状态1：不接受。通过空转换到 self 将 S 推入空堆栈。对于 G 中的每个产生式，将空转换到 self，但将产生的字符串向后推入堆栈。读取终端符号 x 时，空转换到 self，其中 x 位于堆栈顶部。在空堆栈上空转换到状态 2。

状态 2：在没有更多输入且堆栈为空时接受。

操作原理：堆栈用于通过向后写出推导，然后在读取输入时将其弹出，来推导语法语言中的字符串。如果输入用完并且堆栈为空，则可以转到状态 2 并接受。

Answer 2

给定一些带有起始S的CFG，您希望能够仅将起始S添加到PDA的堆栈一次，因为如果您“通过空转换到sef将S推入空堆栈”，那么您可以推入无限多个S，这不再是相同的语言。 即这行不通：(q,ε,ε) ->(q, S)

所以诀窍是进行转换：

(q,ε,$) ->(q,SZ)

其中 $ 是开始底部堆栈符号，Z 是一些虚拟变量，将用作新的底部堆栈符号。这不允许您多次重新执行上述转换。 现在，对于每个产生式 A -> x，其中 x 可以是您拥有的符号或变量的任意组合：

(q,ε,A) -> (q,x)

对于每个符号 c，您还必须有： (q,ε,c) -> (q,c)

最后，可以添加到接受状态 q1 的转换

(q,ε,Z) -> (q1,Z)

这会强制堆栈在进入接受状态之前为空。 这将为任何 CFG 创建具有两种状态的 PDA