NPDA具有确切的2个状态，可能需要3个转换到最终状态 [英] NPDA with exactly 2 states that might need 3 transitions to final state

问题描述

比方说，我们要绘制一个接受N语言的NPDA的两个状态的过渡图.我们还要说这个NPDA将恰好具有2个状态.我的想法是在第一状态下进行所有操作，然后将第二状态用作最终结局.像这样:

Let's say we want to draw the transition graph with two states of a NPDA that accepts that language L. And let's also say that this NPDA will have exactly 2 states. My thinking on this would be to do everything in the first state then use the second state as the grand finale. Like so:

但是我不确定lambda转换是否会导致q1，或者是否有更好的方法来执行此操作，这可能是更好的方法，因为我正在尝试自己教这一点.也许有人可以让我回到这里?

But I'm not sure that the lambda transitions will result in q1 or if there is a better way to do this, which there likely is a better way since I'm trying to teach this to myself. Perhaps someone can get me back on track here?

推荐答案

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

You almost got it. You just missed the n>=1 requirement, since your current NPDA will also accept "acb". And you don't need (b,4)/5, since stack symbol 5 won't be used anyway.

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

So you need another stack symbol between 1 and 2 to denote whether we have seen "b" before "c".

q0-q0         q0-q1
(a,Z)/1Z     (b,3)/λ
(b,1)/2      (b,4)/λ
(b,2)/2      (b,5)/λ
(c,2)/3
(b,3)/4
(b,4)/5

这篇关于NPDA具有确切的2个状态，可能需要3个转换到最终状态的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！