形式语言与自动机

1、形式语言与自动机理论Formal Languages and Automata Theory朱保平朱保平南京理工大学计算机学院南京理工大学计算机学院形式语言形式语言形式语言 形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。究语义。- 将语言看做句子的集合将语言看做句子的集合- 将句子看做字母按照一定规则组成的字符串将句子看做字母按照一定规则组成的字符串- 根据规则的形式区分语言类根据规则的形式区分语言类; ;- 大部分问题都可转化为判定某个句子是否属于某个语言的问题大部分问题都可转化为判定某个句子是否属于某

2、个语言的问题 发展过程发展过程克林克林(Kleene)在在1951-1956年间，在研究神经细胞中建立了自动机年间，在研究神经细胞中建立了自动机来识别语言。来识别语言。1956年，乔姆斯基年，乔姆斯基(Chomsky)从产生语言的角度研究语言。从产生语言的角度研究语言。L*，文法文法(grammar)。1959年，乔姆斯基证明了文法与自动机的等价性。年，乔姆斯基证明了文法与自动机的等价性。自动机自动机理论自动机理论自动机理论研究抽象计算装置或自动机理论研究抽象计算装置或“机器机器”。 以状态自动机为基础，建立抽象机器模型；以状态自动机为基础，建立抽象机器模型； 研究机器能做什么，不能做什么，从

3、而定义划分可计算研究机器能做什么，不能做什么，从而定义划分可计算问题和不可计算问题。问题和不可计算问题。 发展过程发展过程 1930s，图灵提出图灵机模型；，图灵提出图灵机模型； 19401950s，有限状态自动机方面的研究；，有限状态自动机方面的研究； 1969年，库克分离出了能有效解决的问题和难解问题。年，库克分离出了能有效解决的问题和难解问题。形式语言与自动机理论的应用有限状态自动机是描述许多重要硬件和软件的有用模型。只有有限个有限状态自动机是描述许多重要硬件和软件的有用模型。只有有限个状态，使得可以用有限的资源来实现。状态，使得可以用有限的资源来实现。 字符串匹配算法字符串匹配算法(K

4、MP) 词法分析器词法分析器 设计和检验数字电路行为的软件设计和检验数字电路行为的软件 其它一些软件，如通信协议验证其它一些软件，如通信协议验证 与有限自动机有关的两种符号表示与有限自动机有关的两种符号表示 文法：设计处理递归结构数据的软件的模型文法：设计处理递归结构数据的软件的模型 正规表达式：与自动机描述的字符串模式等价正规表达式：与自动机描述的字符串模式等价 自动机是研究计算复杂性的必要基础自动机是研究计算复杂性的必要基础 可判定性问题：可判定问题和不可判定问题可判定性问题：可判定问题和不可判定问题 可处理性问题：一般问题和难解问题可处理性问题：一般问题和难解问题计算机与人脑观点一：计算

5、机的能力不如人脑的能力观点一：计算机的能力不如人脑的能力 计算机无法解决不可判定问题；计算机无法解决不可判定问题； 人脑能够部分解决不可判定问题；人脑能够部分解决不可判定问题；例如：判定任意一个程序是否输出例如：判定任意一个程序是否输出“hello world”。 观点二：计算机的能力与人脑的能力相当观点二：计算机的能力与人脑的能力相当 人脑由神经元细胞构成，每个神经元相当于一个有限状态自动机，神人脑由神经元细胞构成，每个神经元相当于一个有限状态自动机，神经经元之间的连接是不断变化的，所以人脑相当于一个极其复杂的不断变化的元之间的连接是不断变化的，所以人脑相当于一个极其复杂的不断变化的有限状态

6、自动机；有限状态自动机； 计算机能够模拟所有图灵机，也就能够模拟所有有限状态自动机。计算机能够模拟所有图灵机，也就能够模拟所有有限状态自动机。第一章语言 1.1 1.1 语言的定义语言的定义 语言学家语言学家chomsky,chomsky,最初从定义语言的角度研究语言最初从定义语言的角度研究语言.1956.1956年年, ,他将他将语言语言L L定义为定义为字母表字母表中的字符组成的一些中的字符组成的一些串的集合串的集合: : 字母表上按一定规则定义一个字母表上按一定规则定义一个文法文法, ,该文法所能产生的所有的句该文法所能产生的所有的句子组成的集合就是该文法定义的子组成的集合就是该文法定义

7、的语言语言. .*L1.2 基本概念1.语言研究的三个方面语言研究的三个方面（1）表示）表示representation：无穷语言的表示无穷语言的表示（2）有穷描述）有穷描述finite description：研究的语言要么是有穷的，要么是可：研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。数无穷的，这里主要研究可数无穷语言的有穷描述。（3）结构）结构structure：语言的结构特征语言的结构特征2.字母表字母表alphabet字母表是一个字母表是一个非空有穷非空有穷集合，字母表中的元素称为该字母表中的符号。集合，字母表中的元素称为该字母表中的符号。例：例：

8、0,1等。等。3.字母表的积运算字母表的积运算 1 1 2ab a 1 1,b 2 2例：例： 1 1 0,1， 2 2a,b,c 1 1 2 =0a,0b,0c,1a,1b,1c4.字母表字母表 的的n次幂次幂 0 为空串为空串 n n-1 的正闭包：的正闭包： 2 3 4 的克林闭包：的克林闭包： 0 0 1 2 3 例：例： 0,1 +0,1,00,01,10,11,000,001， * ,0,1,00,01,10,11,000,001，直观定义：直观定义： *x|x是是 中的若干字符连接而成的字符串中的若干字符连接而成的字符串 x|x是是 中至少一个字符连接而成的字符串中至少一个字符连

9、接而成的字符串5.句子句子 sentence 是一个字母表，对于是一个字母表，对于 上的任何元素上的任何元素x，x叫做叫做 上的一个句子。上的一个句子。6. 句子的长度句子的长度 x ,句子句子x中字符出现的总个数中字符出现的总个数,记为记为|x| ,长度为零的字符串长度为零的字符串称为空句子称为空句子.用用 表示表示. 7. n语言语言:对于任意的对于任意的 ,L称为字母表称为字母表上的一个语言上的一个语言. .对于任意对于任意一个一个xL,xL,x叫做叫做L L的一个句子的一个句子. .n例例: =0,1上不同的语言上不同的语言:n00,11n0,1n0,1,00,11n001,01,00

10、01,10n00,11*n00,1*1n0,1*1110,1*L1.3语言的有限描述 递归定义是解决无穷语言的有穷描述的最好方法递归定义是解决无穷语言的有穷描述的最好方法. . 递归定义的三要素递归定义的三要素: : (1) (1) 基本条款基本条款 (2) (2) 归纳条款归纳条款 (3) (3) 最小性条款最小性条款1.3语言的有限描述例例1：a,b上的所有以上的所有以a打头，长度为偶数的句子。打头，长度为偶数的句子。设设L是满足以上条件的语言，是满足以上条件的语言，L中元素满足如下条件：中元素满足如下条件： （1）aa,ab L （2）若）若u L,则则uaa,uab,uba,ubb L

11、 （3）L中的每个句子是有限使用（中的每个句子是有限使用（1）（）（2）所得。）所得。例例2：a,b上没有两个连续上没有两个连续b的所有句子。的所有句子。设设L是满足以上条件的语言，是满足以上条件的语言，L中元素满足如下条件：中元素满足如下条件：（1） ,b L（2）若）若u L,则则ua,uab L（3）L中的每个句子均是有限次使用（中的每个句子均是有限次使用（1）（）（2）所得。）所得。1.3语言的有限描述例例3：La,bbba,b L表示所有含有表示所有含有bb的的a,b的字符串。的字符串。例例4：Laa,bb,ab,ba L表示所有长度为偶数的字符串。表示所有长度为偶数的字符串。1.4

12、正规语言及其表示（1）定义：定义： 上的正规语言，满足下列定义：上的正规语言，满足下列定义：（1） 和和为为 上的正规语言。上的正规语言。（2）对于）对于 a,a为为 上的正规语言。上的正规语言。（3）若）若X，Y为为 上的正规语言，则上的正规语言，则XY，XY，X也是也是 上的正规语言。上的正规语言。（4）所有）所有 上的正规语言均是有限次使用（上的正规语言均是有限次使用（1）（）（2）（）（3）而得。）而得。定义：设定义：设 为一字母表，为一字母表， 上的正规式由如下定义：上的正规式由如下定义：（1） 和和都是都是 上的正规式。上的正规式。（2）任何）任何a，a是是 上的正规式。上的正规式

13、。（3）u和和v是是是是 上的正规式，则上的正规式，则u|v,uv,u为为 上的正规式。上的正规式。（4）所有所有 上的正规式均是有限次使用（上的正规式均是有限次使用（1）（）（2）（）（3）而得。）而得。正规语言和正规式一一对应正规语言和正规式一一对应1.4正规语言及其表示（2）设设 =a，b， 上的正规式和相应的正规集有：上的正规式和相应的正规集有：正规式正规式 正规集正规集 a a a b a，b ab ab a* ，a，aa，aaa， a*b b，ab，aab，aaab，（a b）* ，a，b，aa，bb，ab，ba，a和和b的任的任 意符号串意符号串1.4正规语言及其表示（3）已知字

14、母表已知字母表a,b，试构造其上的正规式，试构造其上的正规式（1）以）以aa打头的所有符号串的集合。打头的所有符号串的集合。aa(a|b)*（2）以）以aa结尾的所有串的集合。结尾的所有串的集合。 (a|b)* aa（3）每个）每个a有一个也仅有一个有一个也仅有一个b紧跟其后的所有串的集合。紧跟其后的所有串的集合。 b *(ab) *（4）每个）每个a有一个至少有一个有一个至少有一个b紧跟其后的所有串的集合。紧跟其后的所有串的集合。 b *(abb *) *（5）至少包含一个）至少包含一个a且且 每个每个a都有都有b紧跟其后的所有串的集合。紧跟其后的所有串的集合。 b *ab(b|ab) *1

15、.4 正规式的性质正规式的性质 （1）r s=s r （2）r （s t）=（r s） t （3）（）（rs）t=r（st） （4）r（s t）=rs rt （s t）r=sr tr （5） r=r r =r2 文法与语言例例1：已知语言：已知语言L a,b*且且 中中a的个数为偶数的个数为偶数SaA （A中中a的个数为奇数，的个数为奇数，b任意）任意） SbS (S中中a的个数为奇数，的个数为奇数，b任意）任意） A aS bA例例2：已知语言已知语言L a,b*且且 中中a，b的个数为相同的个数为相同 SaA bB A bS aAA BaS bBB例例3： L（G（S）= | 0,1* 其

16、中其中 中中0的个数为偶数且如果存在的个数为偶数且如果存在1的话必须至少有两个连续的的话必须至少有两个连续的1 S0A（0奇，奇，1符合题意）符合题意） S11B（0偶，偶，1任意）任意） A0S A1C（0奇，奇，1打头）打头） B0D（0奇，奇，1任意）任意） B1B （0偶，偶，1任意）任意） C1D （0奇，奇，1任意）任意） D0B （0偶，偶，1任意）任意） D 1D （0奇，奇，1任意）任意） 例例4：L（G（S）= | 0,1* 其中其中 中至少包含一个中至少包含一个1且且 每个每个1都有都有0紧跟其后紧跟其后 S 1A（A为为0打头，打头，1符合题意）符合题意） S 0S A

17、 0B （B为为 0任意，任意，1符合题意）符合题意） B 0B B 1A（ A为为0打头，打头，1符合题意）符合题意） 例例5：L a Ra,b，其中，其中 R为为 的逆的逆S a aSa bSb Example 6:Construct a grammar over a,b,c whose language is anb2ncm|n,m0Example 7: Construct a grammar over a,b,c whose language is anbmc2n+m|n,m0 S aScc aBcc B bBb bbExample 8: Construct a grammar ove

18、r a,b,c whose language is anbmci|0n+mi S aSbcc B A A aAc C B bBc C C aC Example 9: Construct a grammar over a,b whose language is anbm|0nm2n S aSb aSbb 右线性文法右线性文法：文法中每条规则形如：文法中每条规则形如A a或或A aB，其中，其中a为终为终结符或结符或 ，A，B为非终结符。为非终结符。左线性文法左线性文法：文法中每条规则形如：文法中每条规则形如A a或或A Ba，其中，其中a为终为终结符，结符，A，B为非终结符。为非终结符。例例 ：

19、给出语言：给出语言Lan bm ck n,m,k=0的左线性和右线性文的左线性和右线性文法。法。左线性文法为：左线性文法为：S Sc B B Bb A A Aa 右线性文法为：右线性文法为： S aS B B bB C C cC 第3章 上下文无关语言3.1 上下文无关文法一、定义:文法G=(V,T,P,S)称为上下文无关文法,如果P中的每一条规则具有形式:其中AV,x(VT)*例：文法G=（S，A，B，S，P），产生式这个文法是上下文无关的，它的推导是： S aSa aaSaa aabSbaa aabbaa其定义的语言为其定义的语言为xA |bSbaSaS *,|)(baGLR试证明语言 是

20、上下文无关的。证明：当nm时： n0,j0不是正规语言。不是正规语言。证明：设证明：设 ai bj cj |i0,j0是正规语言。是正规语言。对于泵长度对于泵长度N，考虑，考虑z=a bN cN .根据泵作用引理，根据泵作用引理，z可分解为如下两种形式：可分解为如下两种形式：（1）a v，有，有u v w abi bj bN-i-jcN (其中，其中，i+j0) 考虑考虑uv2w= abibjbjbN-i-jcN =abNbjcN L (2)a v,有有u v w abi bN-icN (其中，其中，i0,j0不是正规语言。不是正规语言。例例2：试证明语言：试证明语言L ai bj c2j |

21、i 0,j 0不是正规语言。不是正规语言。 6上下文无关文法与下推自动机 语言语言ai bi|i0是不能被有穷自动机所接受的。要接受这个语言，机是不能被有穷自动机所接受的。要接受这个语言，机器需要记录某一器需要记录某一a的有限次数，有限状态机的约束不允许自动机的有限次数，有限状态机的约束不允许自动机“记住记住”输输入入串中串中a的个数。因此我们需要定义一个新型自动机，它由一个下推栈加上一的个数。因此我们需要定义一个新型自动机，它由一个下推栈加上一个有限自动机组成，称为下推自动机（个有限自动机组成，称为下推自动机（PDA）。）。 6.1 下推自动机(1) 定义：下推自动机（定义：下推自动机（pu

22、shdown automation)是一个七元组是一个七元组（Q， ， ， ，q0，z,F）,其中其中Q是一有穷状态集，是一有穷状态集， 为一有穷字母表，为一有穷字母表， 为一有一有穷下推集，为一有一有穷下推集， q0为开始状态，为开始状态，z为下推字符为下推字符,F Q是终止状态集，是终止状态集， 是从是从Q （ ） （ P ）到）到Q （ P ）的转移函数。）的转移函数。一个一个PDA有两个字符集：输入字符串有两个字符集：输入字符串 它由输入字符串组成，有一个栈它由输入字符串组成，有一个栈字符集字符集P，它的元素存在栈中。，它的元素存在栈中。A 表示以表示以A为栈顶元素的栈，空栈被表示为栈

23、顶元素的栈，空栈被表示为为 。PDA的计算开始于状态的计算开始于状态q0 ，输入在输入带上且栈为空。，输入在输入带上且栈为空。PDA的当前状态、输入符号和栈顶符号决定自动机的转换。转换函数的当前状态、输入符号和栈顶符号决定自动机的转换。转换函数 列出所有给定状态、符号和栈顶元素的所有可能的转换。列出所有给定状态、符号和栈顶元素的所有可能的转换。 （ qi，a,A)=qj,B,qk,C表示当前状态为表示当前状态为qi，输入符号为，输入符号为a，栈顶符号为栈顶符号为A时的两种可能的转换。时的两种可能的转换。 6.1 下推自动机(2) qj,B （ qi，a，A) new state current

24、 stack top new stack top current input symbol current state 表示表示 i)状态由状态由qi换为换为qi ii)处理字符处理字符a,输入带向前移动输入带向前移动iii）栈顶）栈顶A退栈退栈iv）B进栈。进栈。6.1 下推自动机(3) 一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。转换函转换函qj,B （ qi，a，A) 表示如下：表示如下： a A/Bqi qj 符号符号/表示表示B代替代替A 可以出现在输入字符和栈顶位置，分别三种转换函数。可以出现在

25、输入字符和栈顶位置，分别三种转换函数。（1） qi, （ qi， ，A) （输入位置是（输入位置是 ） A/ A出栈出栈 qi 6.1 下推自动机(4) （2） qi, A （ qi， ， ) （输入位置是（输入位置是 ） /A （A压栈，不改变输入状态）压栈，不改变输入状态） qi（3） qj, （ qi， a ， ) a / (等价于有限自动机，转换由状态和输入符号决定）等价于有限自动机，转换由状态和输入符号决定） qi qj一个一个PDA可表示为一个三元组可表示为一个三元组qi, , ， qi是机器状态，是机器状态， 为未处理为未处理的输入串的输入串, 为栈顶。为栈顶。 qi, , qj

26、,v, 表示表示qj,v, 由由qi, , 经一步转换而得。经一步转换而得。6.1 下推自动机(5) 例例1：构造一个：构造一个PDA接受语言接受语言ai bi |i=0 M: Q=q0, q1 a /A b A/ b A/ =a,b =A F=q0, q1 (q0,a, )=q0,A (q0,b, A)=q1, (q1,b, A)=q1, q0,aabb, q0,abb, A q0,bb, AA q0,b, A q0, , q0 q16.1 下推自动机(6) 定义：设定义：设M （Q， ， ， ，q0，F）为一）为一PDA，字符串，字符串 被被PDA接受，如果接受，如果q0, , * * q

27、i, , , qi F（终态的集合）（终态的集合）例例2：PDAM接受语言接受语言 c R| a,b*M: Q=q0, q1 =a,b,c =A,B F= q1 (q0,a, )=q0,A b b /B b B/ (q0,b, )=q0, B a /A a A/ (q0,c, )=q1, q0 c / q1 (q1,a, A)=q1, (q1,b, B)=q1, 6.1 下推自动机(7) 例例3：PDAM接受语言接受语言 ai |i=0 ai bi |i=0 a /A b A/ q0 b A/ b A/ q1 / q2 A/ 6.1 下推自动机(8) 例例4:含有相同个数的含有相同个数的0和和

28、1的所有的的所有的0,1串。串。思想：用栈记录思想：用栈记录0 0和和1 1个数的差。当个数的差。当1 1比比0 0多时，栈中全部为多时，栈中全部为A A，且，且A A的个数等的个数等于于1 1比比0 0多的个数；当多的个数；当0 0比比1 1多时，栈中全部为多时，栈中全部为B B，且，且B B的个数等于的个数等于0 0比比1 1多的多的个数。个数。 M=(q,p, 0,1, A,B,Z, M=(q,p, 0,1, A,B,Z, , q, Z, p), q, Z, p)，其中，其中 (q,(q, ,Z)=(p, ,Z)=(p, ) ) 接受接受 ，读完字符串后栈中没有，读完字符串后栈中没有A

29、A或或B B，转到终止状态，转到终止状态 (q,1,Z)=(q, A) (q,1,Z)=(q, A) 在前面在前面0 0和和1 1个数相等的时候又读到个数相等的时候又读到1 1，则在栈中压入，则在栈中压入1 1个个A A (q,0,Z)=(q, B) (q,0,Z)=(q, B) 在前面在前面0 0和和1 1个数相等的时候又读到个数相等的时候又读到0 0，则在栈中压入，则在栈中压入1 1个个B B (q,1,A)=(q, AA) (q,1,A)=(q, AA) 在前面在前面1 1比比0 0个数多的时候又读到个数多的时候又读到1 1，则在栈中再压入，则在栈中再压入1 1个个A A (q,0,A)

30、=(q, (q,0,A)=(q, ) ) 在前面在前面1 1比比0 0个数多的时候又读到个数多的时候又读到0 0，则从栈中弹出，则从栈中弹出1 1个个A A (q,1,B)=(q, (q,1,B)=(q, ) ) 在前面在前面0 0比比1 1个数多的时候又读到个数多的时候又读到1 1，则从栈中弹出，则从栈中弹出1 1个个B B (q,0,B)=(q, BB) (q,0,B)=(q, BB) 在前面在前面0 0比比1 1个数多的时候又读到个数多的时候又读到0 0，则在栈中压入，则在栈中压入1 1个个B B根据文法构造根据文法构造 G G：S S1S0S | 0S1S | 1S0S | 0S1S

31、| 构造语言的 NPDA30 |nmnbaLmn6.2 下推自动机与上下文无关文法一个上下文无关语言都存在一个NPDA能够授受它;反之亦然.1.上下文无关语言相应的下推自动机 对于每一个上下文无关文法语言都存在一个NPDA可以接受它.它的基本思想是构造一个NPDA能够以某种方式对于该语言中任何符号串产生一个最左推导.为了对命题稍做简化,我们可以假定上下文无关语言是由格里巴克范式生成的.定理:对于任何的上下文无关文法语言L,存在一个NPDA M使得L=L(M).已知文法SaSbb|a,构造NPDA.首先修改文法转换为格里巴克范式: SaSA|a AbB Bb2.下推自动机相应的上下文无关文法 使

32、用文法模拟PDA的转移,这也就是说使句型中的变量部分反映栈的内容,而已处理的输入作为句型的仅含终结符前缀.为了简单,我们将假定问题中的NPDA满足如下条件:(1)它只有一个终态qf,且当且仅当栈空是才进入终态.(2)所有转移函数的形式应该是(qi,a,A)=c1,c2,cn,其中C=(qj, )或C=(qj, BC)定理:对于任何一个NPDA M,如果L=L(M),则L是上下文无关语言.6.36.3 上下文无关语言的性质上下文无关语言的性质( (泵引理）泵引理）(1)(1) 定理：定理：(2型语言的泵作用引理型语言的泵作用引理) ) 设设L L是上下文无关语言，存在常数是上下文无关语言，存在常

33、数p p，如果，如果LL，且，且p,p,则则可以可以写为写为uvwxyuvwxy，其中其中i) vxi) vx，ii)vwxpii)vwxp iii) uvuvi iwxwxi iyLyL (i0i0 ) 线性语言的泵作用引理是说，在正规集合中，每个足够长的字符串都包线性语言的泵作用引理是说，在正规集合中，每个足够长的字符串都包含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串还是在原正规集中。还是在原正规集中。 2 2型语言的泵引理是说，有两个靠得很近的子串，它们可以重复任意型语言的泵引理是说，有两个靠得很近的子串

34、，它们可以重复任意多次（但二者重复的次数相同），所得的新串依然属于该多次（但二者重复的次数相同），所得的新串依然属于该2 2型语言。型语言。 6.36.3上下文无关语言的性质上下文无关语言的性质( (泵引理）泵引理）(2)(2) 证明证明 L L an bn cn | n n1 1 不是不是2 2型语言型语言. .证：假设证：假设L L是是2 2型语言。型语言。 取常数取常数p p， ap bp cp, ,3p3pp p 将将写成写成uvwxyuvwxy 其中其中vx1 vx1 且且 vwxvwxp p 考虑考虑vwxvwx在在中所处的位置：中所处的位置： 如果如果v v含有含有a a，x x

35、含有含有c c， apbpcp 则有则有vwxvwx最小为最小为a a bp c c p+2 pp+2 p 不满足泵作用引理的条件。不满足泵作用引理的条件。 如果如果v,xv,x都含有都含有a a，（，（b b或或c c） ap bp cp 可写成可写成a ai ap-2-i-j a aj j bp cp v w x v w x 将将v v、x x重复重复2 2次，将有次，将有 = = a2iap-2-i-j a2j bp cp L(a L(a的个数大于的个数大于b b和和c c的个数的个数) ) 与与2 2型语言的假设矛盾型语言的假设矛盾6.36.3上下文无关语言的性质上下文无关语言的性质(

36、 (泵引理）泵引理）(3)(3) 若若v v、x x分别包含分别包含a a和和b b（b b和和c c） 当取当取w w = = a a a a ap-2b b bp-1 cp 时时 u v w x yu v w x y 将将v v、x x重复重复2 2次，次， 将有将有 = a = a a a2 2 ap-2b b2 2 bp-1 cp L L v w x v w x （其中其中a a、b b个数将大于个数将大于c c的个数）的个数） 与与2 2型语言假设矛盾。型语言假设矛盾。 综上，综上，L L不是不是2 2型语言。型语言。 6.36.3上下文无关语言的性质上下文无关语言的性质( (泵引理

37、）泵引理）(4)(4) 证明：证明：La*| 的长度为质数不是上下文无关文法。的长度为质数不是上下文无关文法。证明：设证明：设L是上下文无关文法，是上下文无关文法，n是一个大于泵作用引理中是一个大于泵作用引理中p的素数的素数. 由泵作用引理知：由泵作用引理知： an必须分解为必须分解为uvwxy满足泵引理的条件令满足泵引理的条件令mu|+|w|+|y|,任意串任意串uvuvi iwxwxi iy y的长度是的长度是m+i(n-m).m+i(n-m). |uv |uvn+1n+1|+|wx|+|wxn+1n+1|+|y|=m+(n+1)(n-m)=n(n-m+1)|+|y|=m+(n+1)(n-

38、m)=n(n-m+1) 故故uvuvi iwxwxi iy y的长度不是质数，所以的长度不是质数，所以L L不是上下文无关文法。不是上下文无关文法。 证明语言证明语言an bjanbj |i,j=0不是上下文无关语言。不是上下文无关语言。6.36.3上下文无关语言的性质上下文无关语言的性质( (封闭性）封闭性） （1 1）设有）设有2型语言型语言L1、L2，则则L1L2，L1L2，L1* 为为2型语言。型语言。（2 2）2 2型语言对交不封闭型语言对交不封闭 反证：取反例反证：取反例 L1L1aan n b bn nc cmm m,nm,n1 21 2型型 L2L2 a am m b bn n

39、c cn nm,nm,n1 21 2型型 L1L1L2L2aan n b bn nc cn n n n1 1 不是不是2 2型型 （3 3）2 2型语言对补运算不封闭型语言对补运算不封闭L1L1L2= L1L2= L1L2L2若对补封闭，则对交封闭。若对补封闭，则对交封闭。已知对交不封闭，已知对交不封闭，对补不封闭对补不封闭 第七章 图灵机标准图灵机 图灵机可以看成一个一维单元组,其中每一个单元可以包含一个符号.该单元组可以在两端无限扩展,因此它能够存储无穷信息.这些信息可以以任意顺序读取和修改,我们称这样的存储机制为带(tape),因为它与实际计算机的磁带十分类似.图灵机的定义图灵机是一种自

40、动机，它采用带作为临时存储，带可以划分为若干单元，其中每一个单元包含一个符号。与带关联的是读写头(read-write head)，它能够在带上左右移动，并且每次能够读写一个符号。下图图灵机的直观描述。图灵机的直观描述控制部件读写头带图灵机的形式定义 图灵机M由 M=（Q,q0,F)定义，其中： Q是内部状态的集合； 是输入字母表 是符号的有穷集合，称之为带字母表（tape alphabet) 是转换函数 是一个特殊符号，称之为空白符（blank) q0Q是初态，F Q为终态的集合。 在图灵机的定义中我们假定-，也就是说输入字母表是带字母表的子集。转换函数定义如下： ：QQ L，R 它给出了图

41、灵机操作的规则。 的参数是控制部件的当前状态以及即将读入的带符号，它的返回结果是一个新的控制部件状态、一个替换旧带符号的新符号以及一个迁移符号L和R（读头的移动方向：向左或向右）abc内部状态q0迁移前的情形dbc内部状态q1迁移后的情形下图显示了转换函数（q0,a)=(q1,d,R)执行前后的情形： 通常，自动机以一个给定的初态和带上的一些信息开始。然后在转移函数的控制下完成一系列的动作。在这一过程中，带上任何一个单元的内容可能会被检查与修改，最后通过将图灵机置于停机状态（halt state) 使整个过程结束。当图灵机到达一个中没有定义的格局时，将会停机。 一个图灵机及初始格局迁移片断例：

42、Q=q0,q1 =a,b =a,b, F=q1 (q0,a)=q0,b,R (q0,b)=q0,b,R (q0, )=q1,La aq0b aq0b bq0b bq1从一种格局到加一种格局的迁移可采用表示，如(q0,b)=q0,b,R表示为：bq0b bbq0,因此上式的迁移过程为： q0aa bq0a bbq0 bq1b 也记为：q0aa * bq1b标准图灵机的特征1.图灵机的带在左右方向上都没有限制，允许任意数目的左迁移和右迁移。2.由于对每一个格局，最多只定义一种迁移，因而它是确定型的。3.没有特定的输入文件。假定在初始时刻，带上存在特定的内容，其中部份内容可以作为图灵机的输入。同样没

43、有特定的输出设备。当图灵机停机时，带的部份或者全部内容可以作为输出。迁移的形式定义设图灵机M=（Q,q0,F)，则任意串a1ak-1q1akak+1an,其中ai且q1Q ,是M的一个瞬时描述。迁移 a1ak-1q1akak+1an a1ak-1bq2ak+1an 是可能的当且仅当： (q1,ak)=(q2,b,R)迁移 a1ak-1q1akak+1an a1q2ak-1bak+1an 是可能的当且仅当： (q1,ak)=(q2,b,L)针对某一初始格局x1qix2,如果x1qix2 *y1qjay2由于对于任意qj与a， (qj,a)没有意义，则M停机。我们把导致停机状态的格局序列称为计算（

44、computation) 作为语言接受器的图灵机定义：设 M=（Q,q0,F)是一个图灵机，则被M接受的语言为： L(M)=w+:q0w*x1qfx2 对于某个qfF,x1,x2* 例1：基于=0，1，设计一个图灵机，它能够接受正则表达式00*表达的语言。 Q=q0,q1 F=q1 转换函数为： (q0,0)=(q0,0,R) (q0, )=(q1,R)例：对=a,b，设计一个图灵机，它能够接受L=anbn|n1直观上，我们可以用下面方式来解决这一问题。从最左边的a开始，对其进行核对并以某一符号比如x替换它。然后我们让读头继续右移直到碰到最左边的b，对它同样进行核对并经某一符号比如y替换它。在

45、这之一后，我们又左移到最左边的a上，用x替换它，然后移至最左边的b，用y替换它，依此继续。通过这种来回移动，对每个a，我们用b去和它匹配，如果最后没有a和b了，则认为该符号串一定在语言L中。 Q=q0,q1,q2,q3,q4 F=q4 =a,b =a,b,x,y, (q0,a)=(q1,x,R) (q1,a)=(q1,a,R) (q1,y)=(q1,y,R) (q1,b)=(q2,y,L) (q2,y)=(q2,y,L) (q2,a)=(q2,a,L) (q2,x)=(q0,x,R) (q0,y)=(q3,y,R) (q3,y)=(q3,y,R) (q3,)=(q4,R)作为转换器的图灵机 图

46、灵机并不仅仅在语言接受上有用,它同样为我们提供了通用计算机的一个简单的抽象模型.由于计算机的基本目标在于将输入转换为输出,它就象一个转换器的工作一样. 一个计算的输入就是初始时刻带上的空白符号,而计算完成时,带上所有的符号就是输出.这样我们可以将一个图灵机转换器看成函数f的实现.f定义如下:如果对某一个终态qf,e,有 w=f(w) 即:q0w*mqfw定义:对定义域为D的函数f,如果存在一个图灵机M= (Q,q0,F)使得对所有的wD,都有q0w*Mqff(w), qfF 成立,则称该函数是图灵可计算的(Turing-computable)或可计算的(computable)例:设计一个图灵机

47、用于拷贝由1构成的符号串.更确切的说,也就是构造一机器能够执行计算: q0w*qfww 其中w1+直观描述: 1.用x替换每一个1 2.找到最右边的x,用1替换它 3.移至当前带上非空区域的最右端,并创建1 4.重复2和3直到再也没有x为止.其图灵机为: (q0,1)=(q0,x,R) (q0, )=(q1, ,L) (q1,x)=(q2,1,R) (q2,1)=(q2,1,R) (q2, )=(q1,1,L) (q1,1)=(q1,1,L) (q1, )=(q3, ,R)其中q3为唯一的终态. q011x q01x xq0 x q0 xx1 q2 为如下基于a,b的语言构造图灵机:nL=L(

48、aba*b)(b) L=a,b*| |是偶数 （q0,a)= (q0,b)=(q1,R) （q0,)= (q2,R) （q1,a)= (q1,b)=(q0,R)其中F=q2.第八章 图灵机的其它模型1.带不动选择图灵机 在标准图灵机定义中,读写头要么向左移动要么向右移动,而有时为了方便,我们引入第三种选择,即在读写头重写带上单元后位置保持不动,于是人们可以修改标准图灵机得到新的带不动选择的图灵机(Turing machine with stay-option)的定义,办法是将标准图灵机定义中的替换为: :QQ L,R,S S表示读写头位置保持不动.这一改动并没有增强标准图灵机的能力.定理:带不

49、动选择的图灵机类与标准图灵机类等价.证明:因为带不动选择图灵机显然是标准图灵机的扩展,于是任何标准图灵机无疑可以被带不动选择图灵机模拟. 为了证明逆命题,我们令M=（Q,q0,F)为一带不动选择图灵机.用一个标准图灵机M=（Q,q0,F)模拟它.对于M的每一步,模拟机M做如下工作:如果M的读写头向左移动或向右移动,则M的读写头也相应地向左或向右移动;如果M执行了动作S,则M执行两步动作:读写头首先重写单元格并向右移动,然后对新移动到的单元格不做任何修改并向左移动.这一模拟机可以爱过定义由M构造如下:对于每一步转移 （qi,a)=(qj,b,L or R)我们把解释为: （qi,a)=(qj,

50、b, L or R)对于读写头不动的转移 （qi,a)=(qj,b,S)我们把读写头解释为相应的两步转移: （qi,a)=(qjs, b, R) （qjs,c)=(qj, c, L) 其中c很显然,对M的每一个计算,都有对应的M的一个计算,因此M可以模拟M. 模拟是证明自动机等价的一种标准技术. 在介绍其他模型之前,我们对标准图灵机做一点修改,每个带符号可以是一些符号的组合体,而不仅仅是单个符号.在下图中每个带符号都是三个较简单的字母构成的三元组.带上的每个单元划分为三个部分,每部分称为道(track),每个道包含三元组的一个成员.基于这一直观认识,这样的图灵机有时称为多道图灵机(Turing

51、 machine with multiple tracks).但这一观点并没有扩展标准图灵机的定义,因为我们所要做的只是将改为一个新的字母表,其中每个符号包含几个部分.a第一道b第二道c第三道2.单向无穷带图灵机 单向无穷带图灵机器(Turing machine with semi-infinite tape) 可以直观地理解为带只有左边界.这一模型与标准模型同样等价的,区别在于当读写头位于带的左边界时不能向左移动. 不难看出,这一限制并没有影响村准图灵机的能力. 为了用单向无穷带图灵机M1模拟标准图灵机M,我们采用下图所示的带: 模拟带M1有一条双带道,在上道中保存位于M带上某一点右侧单元的

52、内容,如可以选择计算开始时读头的位置作为参考点.在下道中,我们以逆序保存位于M带上参考点左侧的内容.我们可以可以对M1编程.使得当M的读写头位于参考点右侧时, M1使用上道信息; 当M的读写头位于参考点左侧时, M1使用下道信息;M的读写头是否位于参考点右侧可以通过M1的状态分为两部分以辅助进行判断,比如设两类状态分别为QU和QL:当M1处于上道时使用前者,否则使用后者.左边界处的上下道中均包含特殊的结束符#,以便于两个道间的切换. 第一道模拟标准带的右部第二道模拟标准带的左部如:被模拟的图灵机M和模拟机M1分别位于下图所示的格局,并且将要模拟的迁移由（qi,a)=(qj,c,L)生成.模拟机M1先通过转移1（q1i,a)=(q1j,(c,b),L)来进行迁移,其中q1i QU,所以此处只考虑上道信息.此时模拟机在状态q1j QU.因为q1i QU,所以此处只考虑上道信息,此时模拟机在状态q1i QU,看到了符号(#,#),接下来作转移: 1（q1j,(#,#)=(p1j,(#,#),R),其中p1j QLabc参考点q1iqi # a # b# a# c# c# b# b# bq1iq1jp1j3.离线图灵机 如果我们在模型中加入输入文件,我