我正在学习 PDA 测试，我想知道如何设计一个识别以下语言的下推自动机:
L = {a^max(0,n-m)b^n a^m| n,m >=0}
如何设计一个转换函数来识别 n-m 是否大于 0？
如果您有一些已解决此级别练习的类(class) Material ，请添加一个链接。
最佳答案
您可以根据堆栈顶部的值决定从当前状态转到哪里，您使用堆栈上的符号来记录解析状态。
我认为这是可行的: this 是从输入读取的符号，THIS 是堆栈上的符号。 堆栈底部的符号 X 表示 n <= m 不要将 X 与 Z 混淆，后者是堆栈的初始符号，有助于确定堆栈何时为空。
这个解决方案可能存在一些问题，但总体方法应该是正确的。
...祝你考试顺利:-)
首先，从字符串开头读取所有a符号，并将A添加到每个符号的堆栈中，或者压入X> 如果没有a
然后你读到所有的b符号:
- 如果堆栈为空(Z 在顶部)、B 在顶部或 X 在顶部，则插入另一个B 到堆栈。
- 如果堆栈顶部有A，则将其删除。
最后一步是读取最后的a符号。
- 如果堆栈上有B，请将其移除。
- 如果堆栈上有X，则将其保留在那里
- 如果堆栈为空(Z 在顶部)，那么这一定是字符串的结尾
另一个编辑:
抱歉，如果以上内容不清楚……我会尝试将其形式化。
接受状态是(4)和(5)，起始状态是(1)。而且它是不确定的
以及转换规则:
状态(1):读取第一批a符号
- (1) a； Z/AZ -> (1)
- (1) a； A/AA -> (1)
- (1) ε； A/A -> (2)
- (1) ε； Z/Z -> (2)
状态(2):读取b符号
- (2) b; Z/BZ -> (2)
- (2) b; X/BX -> (2)
- (2) b; B/BB -> (2)
- (2) b; A/epsilon -> (2)
- (2) ε； B/B -> (3)
- (2) ε； X/X -> (3)
- (2) ε； Z/Z -> (3)
状态(3):读取最后一个as
- (3) a; B/无 -> (3)
- (3) ε； X/X -> (4)
- (3) ε； Z/Z -> (5)
状态 (4):如果 m > n，则尾随 as
- (4) a; X/X -> (4)
状态 (5) 用于在 m < n 时接受确切的字符串
(并且要绝对清楚 - 当没有状态的方式并且阅读光标不在单词的末尾时，则该单词不被接受)
通过使用附加状态而不是堆栈符号X，这可能会变得更简单，但我想你可以自己做:-)
关于language-theory - 如何设计这个下推自动机的转换函数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1055098/