automata - NPDA 正好有 2 个状态，可能需要 3 次转换到最终状态

Question

假设我们要绘制具有接受该语言 L 的 NPDA 的两个状态的转换图。并且我们还假设这个 NPDA 将有两个状态。我对此的想法是在第一个状态下做所有事情，然后使用第二个状态作为压轴。像这样：

但是我不确定 lambda 转换是否会导致q1或者是否有更好的方法来做到这一点，这可能是一种更好的方法，因为我正试图自学这一点。也许有人可以让我回到正轨？

Answer 1

你几乎明白了。您只是错过了n>=1要求，因为您当前的 NPDA 也将接受“acb”。而且您不需要 (b,4)/5，因为无论如何都不会使用堆栈符号 5。

因此，您需要另一个介于 1 和 2 之间的堆栈符号来表示我们是否在“c”之前看到了“b”。

q 0 -q 0          q 0 -q 1
(a,Z)/1Z (b,3)/λ
(b,1)/2 (b,4)/λ
(b,2)/2 (b,5)/λ
(c,2)/3
(b,3)/4
(b,4)/5