第五章下推自动机PDA FA识别正语言（右线性语言） PDA识别上下文无关语言
第五章 下推自动机 PDA FA识别正则语言(右线性语言) PDA识别上下文无关语言
FA只能处理正则语言 正则文法生成无穷语言是由于 A->WA 不需要记录w的个数
FA只能处理正则语言 正则文法生成无穷语言是由于 A->wA 不需要记录w的个数
无关文法生成无穷语言 A->aAB 需要记录和耶之间的对应关系 无法用FA的有穷个状态来表示
无关文法生成无穷语言 A->αAβ 需要记录α和β之间的对应关系 无法用FA的有穷个状态来表示
为FA扩充一个无限容量的栈 用栈的内容和FA的状态结合起来 就可以表示无限存储。 这种模型就是下推自动机 Push-Down Automaton--PDA
为FA扩充一个无限容量的栈 用栈的内容和FA的状态结合起来 就可以表示无限存储。 这种模型就是下推自动机 Push-Down Automaton--PDA
PDA作为形式系统最早于1961年 出现在Oettinger的论文中。 与上下文无关文法的等价性由 Chomsky-于1962年发现
PDA作为形式系统最早于1961年 出现在 Oettinger 的论文中。 与上下文无关文法的等价性由 Chomsky于1962年发现