数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究当一个字符串被NPDA接受或拒绝时会发生什么？
如果存在从起始状态到最终状态的某个路径（即指令序列），并且该路径消耗了字符串的所有字母，则非确定性下推自动机 (NPDA) 接受该字符串。否则，NPDA 拒绝该字符串。
NPDA 的语言是它接受的所有字符串的集合。
在以下情况下，输入字符串会被NPDA拒绝：
如果读取输入字符串完成但没有到达最终状态。
如果对于当前状态/栈上的符号/输入符号不存在转换。
如果尝试弹出空栈。
示例
构建一个识别上下文无关语言的NPDA
L = {anbn| n > 0}。
步骤
按照以下步骤构建NPDA：
开始读取字符串，对于每个读取到的a，将一个Y压入栈中。
在第一个b出现时更改状态，并开始为每个b从栈中弹出一个Y。
如果到达输入的末尾并且刚刚清空了栈，则接受字符串。
否则，拒绝。例如，如果在输入结束前栈就为空了——b的数量多于a的数量。
用于 { anbn , n>=0} 的下推自动机
三个状态 - 0（开始）、1、2（最终）
输入字母表 - {a,b}
栈字母表 - { Y,$}
下推自动机如下所示：
此NPDA有六条允许的指令，如下所示：
T1 - (0, a, $, push(Y), 0)
T2 - (0, a, Y, push(Y), 0)
T3 - (0, ∧, $, nop, 2)
T4 - (0, b, Y, pop, 1)
T5 - (1, b, Y, pop, 1)
T6 - (1, ∧, $, nop, 2)
读取$对应于检查栈是否为空。
更新于：2021年6月15日
252次浏览
广告