形式语言 Npda 图

Question

我正在尝试为这种语言绘制一个 npda，但似乎无法得到它

我想知道如何编写 npda 对输入序列 w = aacb 完成的移动序列。并且字符串 w 是否被接受？

谢谢，我似乎无法做到这一点

Answer 1

1. 在不接触堆栈的情况下至少读取两个 a。如果您看到其他任何内容，请崩溃。
2. 继续阅读 a，每阅读一个 a 就将一个 a 压入堆栈。
3. 如果你读了一个c，那么你必须马上读一个b，否则会崩溃。不要更改堆栈。
4. 如果你读了 a b，准备开始一遍又一遍地阅读 (ac)。不要更改堆栈。
5. 如果栈不为空，必须先读a再c，否则崩溃。如果你读了 a 然后读了 c，从栈中弹出一个 a。
6. 继续，直到崩溃或多次读取(ac)后堆栈变空。如果输入已用尽，则接受。否则崩溃。

如果您想查看状态转换图以使其更具体，请告诉我。我鼓励您先尝试自己编写。