language-theory - 我如何设计这个下推自动机的转换函数？

Question

我正在学习 PDA 上的测试，我想知道如何设计一个识别以下语言的下推自动机:

L = {a^max(0,n-m)b^n a^m| n,m >=0} 

如何设计转换函数来识别 n-m大于 0 ?

如果你有一些解决了这个级别练习的类(class) Material ，请放一个链接。

Answer 1

您可以根据堆栈顶部的值决定从当前状态到哪里，您可以使用堆栈上的符号来记录解析状态。

这是我认为这会起作用的方式:
此 是从输入中读取的符号，此 是堆栈上的符号。
符号 X 在堆栈的底部意味着 n <= m
不要混淆 X 与 Z ，这是堆栈的初始符号，有助于确定堆栈何时为空。

此解决方案可能存在一些问题，但总体方法应该是正确的。

...祝你考试好运:-)

首先你阅读所有 从字符串的开头添加符号 一个 到每个堆栈，或推 X 如果没有

然后你阅读了所有 b 符号:

如果堆栈为空( Z 在顶部)， 乙 位于顶部或 X 是在上面，然后你推另一个 乙 到堆栈。

如果堆栈有 一个 在顶部，然后将其删除。

最后一步是阅读最终 符号。

如果有 乙 在堆栈上，将其删除。

如果有 X 在堆栈上，然后将其保留在那里

如果堆栈为空( Z 在顶部)，那么这必须是字符串

的结尾


另一个编辑:

抱歉，如果上述内容不清楚……我会尝试将其正式化。

接受状态为(4)和(5)，起始状态为(1)。它是不确定的

和过渡规则:

状态(1):读取第一批 符号

(1) ; Z / AZ -> (1)

(1) ; 一个 / AA -> (1)

(1) ε； 一个 /一个 -> (2)

(1) ε； Z / Z -> (2)

状态 (2) :阅读 b 符号

(2) b ; Z / BZ -> (2)

(2) b ; X / BX -> (2)

(2) b ; 乙/ BB -> (2)

(2) b ; 一个 /epsilon -> (2)

(2) ε； 乙 /乙 -> (3)

(2) ε； X / X -> (3)

(2) ε； Z / Z -> (3)

状态 (3) : 读取最后 秒

(3) ; 乙 /没有 -> (3)

(3) ε； X / X -> (4)

(3) ε； Z / Z -> (5)

状态 (4) :尾随 如果 m > n

(4) ; X / X -> (4)

状态 (5) 用于在 m < n 时接受确切的字符串

(并且要绝对清楚-当没有状态并且阅读光标不在单词末尾时，则不接受该单词)

通过使用附加状态而不是堆栈符号 ，这可能会更简单一些。 X ，但我想你可以自己做:-)