context-free-grammar - 如何将 cfg 转换为具有 2 个状态的 pda？

Question

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

谁能解释一下我们如何将上下文无关语法（cfg）转换为相应的下推自动机（pda）的算法，只有 2 个状态？

Answer 1

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

状态 2：接受没有更多的输入和空堆栈。

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