计算理论计算理论5章文法与语言3

VIP免费

2025-01-13 3 0 416.33KB 32 页 5.9玖币

侵权投诉

计算理论

第五章自动机与语言

下推自动机

下推自动机﹙ PDA﹚是一种抽象的计算

模型。

下推自动机比有限状态自动机复杂：比

自动机多一个长度不受限制的栈.

下推自动机

PDM 定义：

M=(Q, , , δ, q0, Z, F) ，其中：

Q：有限状态集

 ：栈符号集

：输入符号集

q0Q∈，初始状态

Z ：栈初始符号

FQ，终止状态集

δ ：转换函数 .

下推自动机

确定下推自动机 :

转换函数 : Q×( × )Q× 

非确定下推自动机 :

转换函数 :Q×(× )P (Q× )

定理：

确定下推自动机和非确定下推自动机不等价 .

例

如下下推自动机 M＝({q0,q1,q2,q3}，{a,b} ，

{Z,a} ，δ，q0，Z，{q0,q3}) 是一个 PDA ，其

中δ由以下各式定义：

δ(q0，ε，ε) ＝{<q1，Z>} ，

δ(q1 ，a，ε) ＝{<q1，a>} ，

δ(q1，b，a) ＝{<q2，ε>} ，

δ(q2，b，a) ＝{<q2，ε >} ，

δ(q2，ε， Z) ＝{<q3， ε>}

识别语言： anbn, n0

栈操作：

 弹栈：A  ε

 压栈： ε  A

 弹压栈： A

x

例

 识别语言 {am bm cn, am bn cm | m,n0}

q4q5

,Z

,

a,a

b,a c,

b, c,a

,Z

,

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第五章自动机与语言下推自动机下推自动机﹙PDA﹚是一种抽象的计算模型。下推自动机比有限状态自动机复杂：比自动机多一个长度不受限制的栈.下推自动机下推自动机PDM定义：M=(Q,,,δ,q0,Z,F)，其中：Q：有限状态集：栈符号集：输入符号集q0Q∈，初始状态Z：栈初始符号FQ，终止状态集δ：转换函数.下推自动机确定下推自动机:转换函数:Q×(×)Q×非确定下推自动机:转换函数:Q×(×)P(Q×)定理：确定下推自动机和非确定下推自动机不等价.例如下下推自动机M＝({q0,q1,q2,q3}，{a,b}，{Z,a}，δ，q0，Z，{...

展开>> 收起<<

计算理论计算理论5章文法与语言3.pptx

共32页,预览7页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论计算理论5章文法与语言3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论5章 文法与语言3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论5章文法与语言3