我想知道如何为这种特定的语言设计一个下推自动机。我解决不了这个问题。。
L2={u∈{a，b}*:3*|u|a=2*|u| b+1}
所以‘a’乘以3等于‘b’乘以2加1。
该语言对应的语法类似于：
S -> ab | ba |B
B -> abB1 | baB1 | aB1b | bB1a | B1ab | B1ba
B1 -> aabbbB1 | baabbB1 | [...] | aabbb | baabb | [...]
S生成基本情况(基本上是#a=1=#b的字符串(或b
B生成基本情况+B1(在每个排列中(
B1将2个"a"和3个"b"添加到基本情况(事实上，如果您继续添加这个数量的"a"与"b"，则方程3#a = 2#b + 1将始终为真！(。我没有写完B1，基本上你需要加上2'a'和3'b'的每个排列。我认为你可以自己做：(
当你完成语法后，设计PDA就很简单了。点击此处了解更多信息。
3|u|a=2|u|b+1<>3|u|a-2|u|b=1
为此设计PDA的最简单方法是直接实现这个等式。
对于任何字符串x，设f(x(=3|x|a-2|x|b。然后设计一个PDA，这样，在处理任何字符串x后：
- 堆栈深度始终等于abs(floor(f(x(/3((
- 堆栈顶部的符号(如果有(反映楼层(f(x(/3(的符号您只需要两种堆栈符号
- 当前状态数=f(x(mod 3。当然，您只需要3个状态
根据堆栈顶部的状态号和符号，您可以检测f(x(=1的时间，在这种情况下，PDA接受x作为语言中的字符串。