当前课程知识点:软件理论基础 > 第十二章 Turing机 > 12.2 图灵机的定义 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第二节:图灵机的定义
之前我们讲有限自动机,像DFA、NFA
讲下推自动机
都给出了这些自动机的形式化定义
根据前面介绍图灵机
大致的轮廓
也要给出图灵机的形式化定义
它可以描述成为七元组
Q 是状态集合
∑ 是输入字母的集合
γ 是带符号集合
δ 是状态转移函数
q0 是开始状态
B 是空白符
F 是终态集合
q0 是一个初始状态
它属于状态集中的一个状态
∑ 输入字母,包含在带符号集合里
B是带符号中的空白符
是一个特殊的符号
它不属于输入字母
F是状态集合的子集
最重要的是状态转移函数
状态转移函数δ:是由状态和带符号
到(状态、带符号、左右移)
三元组的映射
是一个确定性的映射
看这样表示的一个图灵机
这图灵机
有 {q0、q1、q2、q3、q4}
五个状态
输入字母是 a 和 b
带符号是a、b、x、y,还有空白符 B
终态是q4
它接受什么样的语言呢?
这个图灵机它接受的语言
是{a的n次方 b的n次方}
这个语言
不是正则语言
但它是下推自动机接受的语言
或者是上下无关语言
图灵机是不是接受这个语言?
给字符串 aabb
看这图灵机是怎么运作的
首先,在 q0
读 a
q0 读 a
执行这个状态转移
把 a 写成 x,右移到 q1
q0读a,a写成x,右移
在q1,读 a
执行的转移是把 a 写成 a
右移到q1状态
q1 读 b
执行这一个状态转移
把 b 写成 y,左移到 q2 状态
q2 读 a
执行这个状态转移
a 写成 a,左移,还是 q2 状态
q2 读的 x,执行这个转移
x 写成 x,右移到 q0
q0,回来了,读a
按之前的操作
a 写成 x,右移到 q1
q1执行的转移是:y写成y、右移
还是到 q1 状态
q1 读 b
b 写成 y,左移到 q2 状态
q2 读 y
y 写成 y
左移还是到 q2 状态
q2 读 x
x 写成 x
右移到 q0 状态
又回到 q0
这个时候,q0 状态读到 y
执行的转移就到这里
y写成y,右移到 q3 状态
q3,读y
y写成y,右移还是到 q3 状态
q3 现在读的空白符
执行这个转移
空白符还是写成空白符
左移到 q4 状态
这个串读完了
最后停在终态 q4
这个串 aabb 接受了
这个图灵机执行的过程
就是把a和b进行匹配
匹配成功
它就被接受了
如果它不匹配 ,则拒绝
这个例子还告诉我们
图灵机可以接受
{a的n次方 b的n次方} 语言
这个语言不是正则语言
DFA、NFA都不接受
但图灵机可以接受
下推自动机能够做的
图灵机也可以做
再看一个例子
有七个状态表示的一个图灵机
这图灵机接受什么字符串?
我们给 001122 字符串
跟我们刚才的操作类似
开始,在初始状态读 0
执行这个转移
0换成 X,右移,到 q1
q1读 0
0 不变,右移,还是到 q1
q1 读 1
1 换成 Y,右移到 q2
q2 读1,1不变,右移到 q2
q2 读 2
2 换成 Z,左移到 q3 状态
q3 读 1
1不变,左移 q3
q3,现在读 Y
Y不变,左移,还是 q3
q3 读 0
0不变,左移,到 q3
q3,现在读 X
X 不变
现在右移,到 q0 状态
我们进行了一轮操作
现在回到 q0
q0 读的是 0
0 换成 X,到 q1 状态
q1,接下来读 Y
Y 不变,右移到 q1
q1,读 1
1 换成 Y,右移,到 q2
q2 读 Z
Z 不变,右移,还是 q2
q2,读 2
2 换成 Z
左移到 q3
q3,读Z
Z不变,左移到 q3
q3,1不变,左移到 q3
q3,Y不变
左移,还是 q3
q3,读的是X
X 不变
右移到 q0
第二轮回到了q0
q0,读的是 Y
执行状态转移是
Y 不变,右移到 q4
q4,再读 Y
Y不变,右移,q4
q4,现在读的 Z
Z不变,右移到 q5
q5,读 Z
Z不变,右移,还是q5
q5,读空白符
空白符不变,右移到 q6
这串读完了
最后落在终态
因此,串 001122 就被接受
这两个例子,它们有相同的地方
也有不同的地方
这接受的字符串
比那个例子的字符串要多一部分
就是后面这一部分
可以验证
这个图灵机它接受的语言
是 {0的n次方 1的n次方 2的n次方}
这个语言,大家很清楚
我们用泵引理证明了
这个语言是非上下无关语言
用下推自动机是表示不出来的
但是,用图灵机它可以接受它
说明图灵机
比下推自动机的表现能力强
这个图灵机,它的整个模型
写出来
七元组,它的状态、输入字母、带符号
状态转移,由这个状态转移图给出来的
空白符、终态
可以用状态转移函数
表示这个图灵机
还可以用状态转移图来表示这个图灵机
之前介绍有限自动机
还有一种表示形式
就是状态转移表
刚才这个图灵机
也可以用状态转移表
这个状态转移表
第一列是状态
第一行是带符号
对一个状态、一个带符号
有一个转移
像 q0 输入 0
0 转成 X
右移到 q1 状态
有的没有转移
因为这是部分转移函数
q0 输入 1 的时候,它没有转移
没有转移,这里就记“一”
这状态转移表
对应了这个状态转移图
它们是一一对应的
有了状态转移表
可以写出状态转移图
反过来也成立
它与状态转移函数也是一一对应的
说明图灵机的表现形式
可以是状态转移函数
可以是状态转移图
也可以是状态转移表
这一节,我们介绍了图灵机的
形式化定义
图灵机
识别字符串的功能
这节内容介绍完毕
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试