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

我遇到了一些问题，我在计算机科学理论研究...如何将cfg转换为具有2个状态的pda？

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

2017-05-08 shahin gh

这个问题会更好地指向[cs.se]，但它会作为重复被关闭。请参阅https://cs.stackexchange.com/questions/19946/how-to-get-2-state-pda-for-cfg或此搜索：https://cs.stackexchange.com/search?q= convert + CFG + to + PDA – rici

我发现他们之前，但他们没有清楚地回答@ rici –

状态1：不接受。通过空转换到自身将S推入空栈。 G中的每个产品都会自动转换为自我，但会将生成的字符串向后推送到堆栈中。在读取终端符号x时将空转换为自身，x在堆栈顶部。在空堆栈上空转换到状态2。

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

操作理论：堆栈用于在语法语言中派生字符串，方法是向后写出，然后在读取输入时弹出它们。如果用完输入且堆栈为空，则可以进入状态2并接受。

来源

2017-05-09 21:00:40 Patrick87

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

回答

相关问题