文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 形式语言及自动机 哈尔滨工业大学(中文版)
侵权投诉

形式语言及自动机 哈尔滨工业大学(中文版)

PartIX

Undecidability

1

问题

非形式的,我们使用问题来表示诸如“一个给定的CFG是否是歧义?”这样的询问.那么一个具体的CFG就是一个问题的实例,一般来说,问题的一个实例就是一个自变量表,每个自变量都表示问题的一个参数.用某个字母表,可以将问题的实例进行编码,我们就能将是否存在解决某一问题的算法这一问题,转化为一个特定的语言是否是递归的问题.可判定问题和不可判定问题

一个问题,如果它的语言是递归的,就称为可判定(decidable)的问题,否则,该问题是不可判定的(undecidable).也就是说,对于不可判定的问题,不存在能够保证停机的图灵机,识别该问题的语言,或者说不存在解决该问题的算法.下面就给出两个不可判定的问题.

2非递归可枚举的语言

我们将使用对角线法证明一个特定的问题是不可判定的,这个问题是“图灵机M接受输入w吗?”.这里的M和w都是该问题参数,并且限制w是{0,1}上的串而M是仅接受{0,1}上的串的图灵机.这个受限的问题是不可判定的,那么较一般的问题也肯定是不可判定的.首先我们需要将问题实例编码为字符串,将问题转化为语言.

2.1

第i个串wi

将全部(0+1) 中的串按长度和字典序排序,那么第i个串就是wi,即

binary(i)=1wi

比如:

ibinary(i)wi

1234567891ε101110010111011110001001ε0100011011000001

·········

2.2图灵机编码与第i个图灵机

将字母表为{0,1}的任意TM用二进制串进行编码.设TMM为

M=(Q,{0,1},Γ,δ,q1,B,F)

再为状态,栈符号和移动方向指派整数编码:

(1)Q={q1,q2,···,q|Q|},指派开始状态为q1,终态为q2,且终态(一定停机)只需一个;(2)Γ={X1,X2,···,X|Γ|},这里总有X1=0,X2=1,X3=B;(3)方向L为D1,方向R为D2.

第1页

你可能喜欢

  • 形式语言与自动机理论
  • 绘画的形式语言
  • 分布式系统
  • 绘画作品
  • 艺术语言
  • 图灵机模型

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email