程序以转换上下文语言以按下自动机?
-
30-09-2019 - |
题
我找不到任何在线上的小程序或程序来将免费语言转换为按下自动机...任何帮助都将不胜感激。
解决方案
手工做非常容易。 PDA已开始国家和最终状态F,它仅有两个州。进行过渡((s,空,空),(f,s)),其中s是CFG的开始符号。对于每个规则x-> y,其中x是一个非终端符号,y是终端和非终端的一个空字符串,进行过渡((f,空,x),(f,y))。最后,对于每个端子符号A,添加规则((f,a,a),(f,empty))。
这是从堆栈上推开启动符号开始的。然后,它用生产规则的右侧替换了在堆栈顶部找到的任何非终端,并匹配并弹出堆栈顶部的任何终端字符。
其他提示
请在以下位置检查代码: https://github.com/p-raj/automataplus. 。它不仅包含将CFG转换为PDA的代码,还包含其他类似任务的代码。
尝试此软: https://github.com/navrkald/regularconvertor。您可以将整个转换CFG的算法置于PDA。它使用QT编写的C ++编写,并在“释放”部分中为Windows构建了可自我执行的二进制文件。
不隶属于 StackOverflow