当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

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

资源类别:文库,文档格式:PDF,文档页数:145,文件大小:351.92KB,团购合买
5.1.1 确定的下推自动机 5.1.2 不确定的下推自动机 5.1.3 PDA接收语言的两种方式 5.1.4 广义PDA和单态PDA 5.2 上下文无关文法和范式 5.3 PDA与上下文无关语言
点击下载完整版文档(PDF)

第五章下推自动机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个数相等}

点击下载完整版文档(PDF)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共145页,可试读30页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有