个性化阅读
专注于IT技术分析

非确定性下推自动机

非确定性下推自动机与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

赞(0) 打赏
未经允许不得转载:srcmini » 非确定性下推自动机
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏