有限自动机理论CH6.ppt

《有限自动机理论CH6.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章图灵机接收能力最强的自动机图灵机(即TuringM--TM)。由A.Turing于1936年提出。TM是可计算性的数学模型研究可计算性(可计算的特点是有穷、离散、机械执行、停机)。为计算机的发展奠定了理论基础。图灵机可以模拟现代的计算机的计算能力。使用图灵机可以解决计算机程序的可计算问题。图灵机的构造技术类似于计算机的编程(设计指令)技术。6.1图灵机的基本模型6.1.1图灵机的定义图灵机的物理模型a1a2a3…aj…anan+1…FSC一个有限状态控制器(FSC)一个外部的存储设备可以向右扩展的无限长度带带上具有左端点，使用“┣”表示图灵机直接扫描输入带上左端点右

2、边的第一个符号。带分解为单元，每个单元可以为空(B)或存放字母表上的字母符号有限状态控制器通过一个读/写头与带进行耦合。带的右边用B标记带的右期间。在某个时刻，有限状态控制器处于某个状态，读/写头将扫描带上的一个单元依照状态和扫描到的带上符号，图灵机将有一个动作如下：有限状态控制器的状态进行改变；把刚刚扫描过的单元上符号擦除掉，并印刷上一个新的符号（有可能印刷上与原来符号相同的符号）；读/写头向左或者向右移动一个单元；或者读/写头不移动。五元式描述动作其中：x，W∈∑′图灵机处于状态q，扫描到符号x，则状态变换为q′，印刷上新的符号W，

3、读/写头向左、或向右或不移动。例6-1用TM接收语言{a2n

4、n≥0}图灵机带上符号串为：┣aaa…aaaB图灵机初始处于状态even，将要扫描第一个a，则//可省略若带上a的个数为偶数，则图灵机经过多个动作后，处于接收状态accept；若带上a的个数为奇数，根据，图灵机将不会停机，可以永远继续下去这与其它的自动机不同，即图灵机可能会导致永不停止的计算。例6-2语言为{a2n

5、n>0}

6、dd，B，R>定义6-1图灵机是一个五元式TM=(Q，∑，q0，qα，δ)Q是有限状态集合；∑是带上字母表的有限集合∑′=∑∪{B}∪A；∑的增广集合，即输入带上符号的集合q0∈Q，是开始状态qα∈Q，是接收状态δ:Q×∑′→Q×∑′×{L,R,N}对于任意的(q，x)∈Q×∑′δ(q，x)=(q′，W，{L，R，N})将δ记为一般形式：或图灵机是一个七元组TM=(Q，，，，q0，B，F)FQ终止状

7、态集合；是带符号集合；B称为空白符；:QQ{R,L,N}定义6-2图灵机的格局IDw1qw2∈w1是读/写头左边带上的符号串q是图灵机当前所处的状态w2是还未扫描到的带上的符号串(∑′)*Q(∑′)*图灵机在格局w1qw2时停机若w1qw2=w1qxw对于无定义。δ(q，x)?定义6-3格局的转换若M在w1qw2上不停机，则如下定义格局的转换：某个时刻，图灵机处于格局w1qw2=r1yqxr2，其中：r1y=w1，(若w1=ε，则y=B，r1=ε)xr2=w2，(若w2=ε，则r2=ε，x=B)使用=>表示图灵机的格局转换若δ（q，x）=(q′，x′，

8、L)，则r1yqxr2=>若δ（q，x）=(q′，x′，N)，则r1yqxr2=>若δ（q，x）=(q′，x′，R)，则r1yqxr2=>r1q′yx′r2r1yq′x′r2r1yx′q′r2使用=>+代表格局的多次变换使用=>*代表格局的任意次变换定义6-4图灵机M=（Q，∑，q0，qα，δ）在字母表∑上接收的语言为L(M)，则L(M)={w

9、存在w1，w2∈(∑′)*有=>*}q0ww1qαw2定义6-5完全的图灵机如果图灵机对于一切输入串都能够停机----完全的图灵机。完全的图灵机接收的语言L称为递归语言(图灵可判定语言)6.1.2图灵机的构造例６-３接收仅有一个1

10、的0、1串TM=({q0，q1，q2},{0，1},q0，{q2},δ)∑′={0，1，B}

11、n>0}思路：当图灵机遇到a时，将a改写为#向右寻找b，找到b，将b改写为#再向左找a…直到所有a都找完。(向左找的a是整个a串最左边的a)指令为①读到一个a，用#代替它，向右找b