电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第05章 下推自动机（简化版）

第五章下推自动机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年发现

与FA比较 PDA具有一个栈存储器 有两个操作： 入栈--将内容压入栈中 出栈--将栈顶元素移出

与FA比较 PDA具有一个栈存储器 有两个操作： 入栈---将内容压入栈中 出栈---将栈顶元素移出

下推自动机物理模型 a 2 3 n+1 存储带 FSC : 栈存储器

下推自动机物理模型 a1 a2 a3 … aj … an an+1 … FSC … 存储带 栈存储器

栈存储器 存放不同于字母的符号 只能对栈顶元素进行操作

栈存储器 存放不同于字母的符号 只能对栈顶元素进行操作

下推自动机动作 FSC当前的状态 根据 输入带上的当前字符 栈顶符号 状态改变 进行 入栈或出栈操作 读头向右移动一个单元

下推自动机动作 FSC当前的状态 输入带上的当前字符 栈顶符号 状态改变 入栈或出栈操作 读头向右移动一个单元 根据 进行

5.1.1确定的下推自动机 例5-1利用栈 识别语言 L={ww∈(a,b),且a、b个数相等

5.1.1 确定的下推自动机 例5-1 利用桟 识别语言 L={w|w∈(a,b) * ，且a、b个数相等}