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.
形式语言及自动机 哈尔滨工业大学(中文版)_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 形式语言及自动机 哈尔滨工业大学(中文版)_理学_高等教育...
形式语言及自动机 哈尔滨工业大学(中文版)_理学_高等教育_教育专区。Part V Context-Free Grammars and Languages 1 上下文无关文法 上下文无关文法在程序设计语言...
形式语言及自动机 哈尔滨工业大学(中文版) 隐藏>> 1 正则表达式 (Regular Expression) 自动机通过识别来定义语言,正则表达式通过规则产生语言 (或表示语言);正则...
形式语言及自动机 哈尔滨工业大学(中文版) 本资料是哈工大自动机课程的中文版,但授课教材是英文版本,望采纳~本资料是哈工大自动机课程的中文版,但授课教材是英文...
形式语言及自动机 哈尔滨工业大学(中文版) 隐藏>> Part VI Pushdown Automata 1 介绍 0 1 1 0 0 1 0 0 1 0 ··· 下推自动机是可以看做带有堆栈的 ...
形式语言与自动机 绪论 45页 免费 我的JAVA五子棋小游戏代... 9页 免费形式语言及自动机 哈尔滨工业...
形式语言与自动机 哈工大正心楼DFA_工学_高等教育_教育专区。Formal Language ... 形式语言与自动机 5 DFA... 33页 免费 哈尔滨工业大学园丁小区... 30页 ...
哈工大形式语言与自动机课件第2讲 授课老师:孙大烈授课老师:孙大烈隐藏>> Finite Automata(FA) Introduction to following contents about three kinds of FA---...
哈工大形式语言与自动机课件第三讲 授课老师:孙大烈授课老师:孙大烈隐藏>> Nondeterministic Finite Automata(NFA) 1. Definition 2. Notation 3. Construction 4...
热门文档