计算理论计算理论2章计算2

VIP免费

2025-01-13 1 0 911.57KB 43 页 5.9玖币

侵权投诉

计算理论

第二章计算

2.1 图灵机模型

定义：图灵机的 M＝(Q, ∑, , δ, B, q0, F) ，其中：

 Q 为状态的有限集合；

 ∑ 为有限字母表，为输入符号集；

 为线性带符号集，∑ ；

 B 空符号， B ，B ∑ ；

 q0Q为初始状态

 FQ是终止状态集 ;

 ：Q× Q×(×{L, R, S}) 为转移函数。

状态控制器

读写头

线性带

例

例6 设计图灵机识别语言

{w#w| w{0,1}*}

基本思路：识别过的都标记为 x，通过不同

状态区分 0和1。

描述

（1）扫描输入；

（2）检查 #左右两边的符号是否相同。

若相同，则通过标记 x消去检查过的符号；

若不同，则拒绝。

（3）左右移动位置，重复（ 2）；

（4）#左边所有符号都消去时，检查 #右边是否还有

符

号。若无，则接受；若有则拒绝。

0x,R

1x,R

0x,R

1x,R

##,R

xx,R

0x,L

xx,L

##,L 11,L

00,L

xx,R

0x,R

1x,R

##,R

1x,L

xx,R

##,R q8

xx,R

BB,L

例

例7：设计一图灵机，识别所有由 0组

成，长度是 2的幂的语言。即 {| n0}

基本思路：从左至右，每隔一个 0消去一个

0，

成对匹配，若无 0可消去，则拒绝。否则重

复上述过程，直至带上只剩下一个 0，则接

受。

描述

输入 w

（1）从左向右扫描，若带子上只有 1个0,

则接受；

（2）若带子上有奇数个 0，则拒绝；否则，

隔一个消去一个 0；

（3）返回到带子最左端，重复 (1) 。

q0q1q2q3

00,R 0x,R 00,R

0x,R

xx,R xx,R xx,R

BB,L

xx,L

00,L

BB,R

BB,L

例

例8 设计一图灵机，识别语言

L={aibjck| i*j=k, 且i,j,k>0}

基本思路：从左至右，每遇到一个 a，消去 j

个c，重复上述过程，直至带上没有 c，则接

受，否则拒绝。

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第二章计算2.1图灵机模型定义：图灵机的M＝(Q,∑,,δ,B,q0,F)，其中：Q为状态的有限集合；∑为有限字母表，为输入符号集；为线性带符号集，∑；B空符号，B，B∑；q0Q为初始状态FQ是终止状态集;：Q×Q×(×{L,R,S})为转移函数。状态控制器q0q5q4q3q1q2读写头线性带例例6设计图灵机识别语言{w#w|w{0,1}*}基本思路：识别过的都标记为x，通过不同状态区分0和1。描述（1）扫描输入；（2）检查#左右两边的符号是否相同。若相同，则通过标记x消去检查过的符号；若不同，则拒绝。（3）左右移动位置，重复（2）；（4）...

展开>> 收起<<

计算理论计算理论2章计算2.pptx

共43页,预览9页

还剩页未读，继续阅读

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

计算理论计算理论2章计算2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论2章 计算2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论2章计算2