NPDA ровно 2 состояний, которые могут нуждаться в 3 перехода в конечное состояние

Question

Допустим, мы хотим нарисовать граф переходов с двумя состояниями NPDA, который принимает этот язык L. И давайте также сказать, что это NPDA будет имеют ровно 2 состояния. Мое мышление об этом было бы сделать все в первом состоянии, а затем использовать второе состояние как грандиозный финал. Как так:

Но я не уверен, что лямбда-переходы будут приводить к q1 или, если есть лучший способ сделать это, что существует вероятность того, лучший способ, так как я пытаюсь научи меня этому. Может быть, кто-то может вернуть меня сюда?

Answer 1

Вы почти получили его. Вы просто пропустили требование n>=1, так как ваш текущий NPDA также примет «acb». И вам не нужно (b, 4)/5, так как символ стопки 5 в любом случае не будет использоваться.

Так что вам нужен еще один символ стека между 1 и 2, чтобы обозначить, видели ли мы «b» до «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