非确定性下推自动机非确定性下推自动机|自动机教

非确定性下推自动机与NFA非常相似。我们将讨论一些接受NPDA的CFG。
【非确定性下推自动机】接受确定性PDA的CFG也接受非确定性PDA。同样，有些CFG只能被NPDA接受，而不能被DPDA接受。因此，NPDA比DPDA更强大。
例：
设计用于回文条的PDA。
解：
假设语言由字符串L = {aba，aa，bb，bab，bbabb，aabaa，… … ]组成。该字符串可以是奇数回文，甚至是回文。构造PDA的逻辑是，我们将一个符号压入堆栈，直到字符串的一半，然后读取每个符号，然后执行弹出操作。我们将进行比较以查看弹出的符号是否与读取的符号相似。无论我们到达输入的末尾，我们都希望堆栈为空。
此PDA是不确定的PDA，因为找到给定字符串的中点并从左侧读取字符串并从右（反向）方向匹配该字符串会导致不确定的移动。这是ID。

文章图片
模拟的Abaaba

δ(q1, abaaba, Z)Apply rule 1 ? δ(q1, baaba, aZ)Apply rule 5 ? δ(q1, aaba, baZ)Apply rule 4 ? δ(q1, aba, abaZ)Apply rule 7 ? δ(q2, ba, baZ)Apply rule 8 ? δ(q2, a, aZ)Apply rule 7 ? δ(q2, ε, Z)Apply rule 11 ? δ(q2, ε)Accept