1

在我的演讲中，我们给出了一个下推自动机的例子，它接受以下语言 {(a^n)(b^n): n 大于或等于零}。

Q - set of states ={s,p,f}
L - alphabet = {a,b}
R - stack = {a}
F - accepting states ={s,f}
D -transition relation ={
(s,a,e),(p,a)
(p,a,e),(p,a)
(p,b,a),(f,e)}

我的问题是为什么状态 p 和 f 是必要的？你不能只使用 state s 吗？

另外我想知道在构建 PDA 时是否有一种方法可以知道您需要多少个状态以及堆栈字母表是什么？还是你只需要直观地解决它？

4

1 回答 1

0

在没有状态 p 的情况下，PDA 将接受具有相同数量的 a 和 b 的任何字符串。

没有非直观的方法可以预先知道状态或转换的数量，因为我们要将非形式描述转换为形式描述，所以没有形式的方法！

于 2015-12-08T05:20:02.920 回答