1、第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26第第11章章 形式语言与自动机简介形式语言与自动机简介 11.1 语言及其表示语言及其表示 11.2 正规语言与有限自动机正规语言与有限自动机 11.3 上下文无关语言与下推自动机上下文无关语言与下推自动机 11.4 图灵机图灵机 11.5 线性界限自动机线性界限自动机 第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.1 11.1 语言及其表示语言及其表示 11.1.1语言语言 语言是一个非常抽象的概念，概括地说，一种语言是由某些字符串组成的集合。为了对语言等给出确切的定义，我们从字母
2、表谈起。由特定的符号组成的有限集合称为字母表。由特定的符号组成的有限集合称为字母表。常见的字母表是由26个英文字母、10个阿拉伯数字、运算符号等组成的集合。0和1两个数字也可以组成字母表。设是一个字母表，由上的符号组成的有穷序列称为上的字符串。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26定义定义11.1 11.1 字母表上满足一定条件的字符串的集合L，称为上的一种语言。例如，若是由26个英文字母(包括大小写)、标点符号和空格组成的字母表，则上那些符合英文单词组成规则和句子生成规则的字符串的集合，便是英语。全部二进制整数也可以看作一种语言，它是字母表0，1上所有字
3、符串的集合。例例1 1 全体3位二进制数组成的字母表0，1上的语言可用列举法表示出来：L000，001，010，011，100，101，110，111。例例2 anbn|n1是字母表a，b上的一种语言，这是用谓词表示法对该语言的一种描述。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.1.211.1.2文法文法 文法是一类语言发生器。从一个文法G可以产生出一个语言L的各个句子，这些句子实际上是字符串。G可以产生的句子的集合，就是一种语言，记为L(G)。文法本身也是一个数学系统。对文法给以不同的定义，可以得到不同的文法体系，这里介绍的文法，也称为短语结构文法。定
4、义定义11.2 11.2 文法是一个四元组G(V，P，S)，其中 (1)V是非终结符号的有限集；(2)是终结符号的有限集，也称字母表，V；(3)P是产生式的集合，P的元素为()，其中(V )*V(V )*，(V )*，表示从可以推导出。(4)S是初始符。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定义定义11.311.3 设G(V，P，S)是一个文法，则 (1)S是句型；(2)若是句型，且是P的一个元素，则也是句型。(3)不含非终结符的句型是语言L(G)的一个句子。下面，我们通过一些例子来说明文法的概念以及由文法产生语言的过程。例例3 3 设G(A，S，0，1
5、，P，S)，其中PS0A1，0A00A1，A。从这个文法可以推导出下面的一些句子：S0A101；S0A100A110011；S0A100A11000A111000111。例例4 4 设G(S，a，b，P，S)，其中PSbSS，Sa。从这个文法中可以推导出下面的句子：SbSSbaSbaa；SbSSbbSSSSbbSaSSbbbSSaSSbbbaaabSSSSbbbaaabaaaa。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定义定义11.4 11.4(1)设G(V，P，S)为一个文法，若对P中的产生式不加任何限制条件，则称G为短语结构文法或0型文法。由0型文法产
6、生的语言称为递归枚举语言或0型语言。(2)设G(V，P，S)为一个文法，如果P中的每个产生式都满足|，则称G为上下文有关文法或1型文法。由上下文有关文法产生的语言称为上下文有关语言或1型语言。(3)设G(V，P，S)为一个文法，如果P中的每个产生式都具有形式A(AV，(V)*)，则称G为上下文无关文法或2型文法。由上下文无关文法产生的语言称为上下文无关语言或2型语言。(4)设G(V，P，S)是一个文法，如果P中的每个产生式都具有形式Aa或AaB(A、BV，a)，则称G为右线性文法；如果P中的每个产生式都具有形式Aa或ABa(A、BV，a)，则称G为左线性文法。右线性文法和左线性文法都称为正规文
7、法或3型文法。由正规文法产生的语言称为正规语言或3型语言。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 11.1.3 11.1.3识别器识别器 对语言进行有限表示的第二种常用方法是识别器。一个语言识别器的结构如图11-1所示。它由三大部分组成：输入带、有限状态控制器和辅助存储器。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 输入带上排列着一个个带单元，每个带单元存放着一个输入字母表中的符号。连接在有限状态控制器上的读写头能在带上读出某个带单元上的符号，有限状态控制器根据读到的符号和辅助存储器中取出的信息决定读写头的动作(左移一格，
8、右移一格或不动，以及需要写上什么符号)，存入存储器的信息及状态的改变等。如果输入带上各单元的符号组成字符串w，识别器从初始格局开始，根据带上的输入字符和辅助存储器上的信息，在状态控制器的控制下，完成一系列动作后，结束在终止格局，那么，就说识别器接受了字符串w，或者说字符串是该识别器可以识别的。由识别器接受的全部字符串的集合，称为该识别器所定义的语言。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 上节指出的四类文法所分别产生的四种类型的语言，即正规正规语言、上下文无关语言、上下文有关语言和语言、上下文无关语言、上下文有关语言和0 0型语言型语言，都存在着对应的识别
9、器类。它们分别为有限自动机、下推自动机、线性界有限自动机、下推自动机、线性界限自动机和图灵机。限自动机和图灵机。研究四类文法及其产生的四类语言性质的学科称为形式语言理论，研究对应的四类识别器的学科称为自动机理论。可见，自动机理论和形式语言理论有着非常密切的关系。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.2 11.2 正规语言与有限自动机正规语言与有限自动机 11.2.1 11.2.1 确定的有限自动机确定的有限自动机 有限自动机是一种具有离散输入和输出系统的数学模型，这种系统具有有限个内部状态。在引入有限自动机的定义之前，我们来看一个例子。有一个人带着一
10、只狼，一只羊和一棵青菜，要从河左岸渡到河右岸。但河中只有一只小船，一次只能装载人和他携带的三者之一过河。考虑到安全问题，当人不在场的时候，狼和羊不能留在河岸的一边，羊和菜也不能留在河岸的一边。如何能使人及其携带的三者都渡过河而羊和菜又不被吃掉呢？第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 我们可以通过状态转换图来求解这个问题。用M、W、G、C等字母分别表示人、狼、羊和青菜。用连字号“”连接上述四个字母形成的序偶来表示状态。如MWGC表示人和他携带的三者都在河的左岸；而MGWC表示人和羊在河的左岸，狼和菜已渡到河的右岸。根据题意，有些状态(如WGMC，MWGC等
11、)是不允许出现的。显然，一种状态能改变成另一种状态，是由于人带着三种携带物之一乘船渡河或者人单独乘船渡河的结果。如果两种状态之间可以通过一次渡河实现转换，便在它们之间加一条连线，并在连线旁分别标上m、w、g、c等小写英文字母，分别表示人单独过河或人携带狼、人携带羊、人携带菜过河。这样问题的求解就变成寻找从初态MWGC到终态MWGC之间的一条有向路。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 从状态转换图中，我们可以归纳出这个系统包含着下面几种要素：有一个状态集(共有10个状态)；有一个
12、状态之间的转换关系(全体有向弧表达了这种关系)；状态之间的转换需要输入字母，全体输入字母组成一个输入字母表(本问题中，输入字母m、w、g、c分别代表不同的渡河情况)；此外还有初始状态和终止状态。这种有限的状态转换系统同有限自动机的情况相类似，下面我们给出有限自动机的定义。定义定义11.511.5 确定的有限自动机(简称DFA)是一个五元组，M(Q，q0，F)，其中 (1)Q是一个有限状态集；(2)是有限的输入字母表；(3)：QQ称为状态转换函数；(4)q0Q初始状态；(5)FQ是终止状态集。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例例1 设有一个确定的有限
13、自动机(DFA)为M(Q，q0，F)，其中Qq0，q1，q2，q3，0，1，Fq0，(q0，0)q2，(q0，1)q1，(q1，0)q3，(q1，1)q0，(q2，0)q0，(q2，1)q3，(q3，0)q1，(q3，1)q2。下面我们考察一下例1，给出DFA的运行情况。假设有一个输入字符串为110101，DFA从初始状态q0开始，读写头扫描到第一个字符“1”，根据状态转换函数(q0，1)q1转换到当前状态q1，接着扫描到第二个字符“1”，并求出(q1，1)q0，然后扫描到第三个字符“0”，求出(q0，0)q2，然后扫描到第四个字符“1”，求出(q2，1)q3，扫描到第五个字符“0”，求出(q
14、3，0)q1，再扫描到最后一个字符“1”，计算出(q1，1)q0。因为是终止状态集F中的一个元素(即q0F)，所以字符串110101是该DFA所接受的。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 一个状态转换函数可以用一个标注有向图来表示。图的结点为状态集Q中的各个元素。对q1，q2Q，若存在a，使得(q1，a)q2，则从q1到q2连一条有向边，并在有向边旁加上标注a；表示一般状态q的结点，用单圆圈内写上q来表示；对终止状态q，用双圆圈写上q表示；在初始状态q0的圆圈外加上一个小箭头并标上“开始”二字。例1的DFA可以表示成如图11-3所示的带标注的有向图。第
15、第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 进一步观察图可以发现一个规律：任何从q0开始又回到q0的有向闭链都必然包含偶数个0和偶数个1；反之，对任意一个含有偶数个0和偶数个1的0，1上的字符串x，都可以在图的状态转换图中找到一条从开始q0又回到q0的有向闭链，使该闭链上各边标注字符的连接为x。因此，我们可以得出结论，一个由0和1组成的字符串x能被例1的DFA接受x中含有偶数个0和偶数个1。我们用L(M)表示自动机M所识别的语言，则有：L(M)x|x0，1*，且x中含有偶数个0和偶数个1第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26
16、 为了形式地描述在输入字符串作用下DFA的行为，我们把状态转换函数的定义扩充一下：把二元函数的第二个自变量由单个字符改为一个字符串，即：Q Q改为：Q*Q。定义定义11.611.6 在DFA中，定义扩充的状态转换函数为：Q*Q，其中(q，w)(qQ，w*)定义为 (1)(q，)q (2)若wxa，则(q，w)(q，x)，a)第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例例2 2 对于例1给出的DFA，试计算(q0，110101)。由定义11.6知：(q0，110101)(q0，11010)，1)，为此，我们应该先计算(q0，11010)，反复用定义11.6，我
17、们可以得到：(q0，11010)(q0，1101)，0)，(q0，1101)(q0，110)，1)，(q0，110)(q0，11)，0)，(q0，11)(q0，1)，1)，(q0，1)(q0，)，1)。由于(q0，)q0，把上面各式逆序计算，可得：(q0，1)(q0，1)q1，(q0，11)(q1，1)q0，(q0，110)(q0，0)q2，(q0，1101)(q2，1)q3，(q0，11010)(q3，0)q1最后可以得到(q0，110101)(q0，11010)，1)(q1，1)q0由于q0F，所以字符串110101是被例1的DFA所接受的。第第11章章 形式语言与自动机简介形式语言与自动
18、机简介 2022-11-26 定义定义11.7 设M(Q，q0，F)为一个有限自动机，则M所识别的语言定义为：L(M)x|(q0，x)F。定义定义11.8 设M(Q、q0、F)为有限自动机，Q上的对偶称为M的格局。其中形如(q0，w)的格局称为M的初始格局；若qF，则(q，)称为M的终止格局或接受格局。我们用“”表示格局间的推出关系。对一个字符串w，检查是否有wL(M)，可以从初始格局(q0，w)开始，设wax，(q0，a)q1，则有(q0，w)(q1，x)，这样一直推导下去，若推导到(q，)时，其中qF，那么，我们说从初始格局(q0，w)推导到终止格局(q，)。这时，wL(M)。如果推导到(
19、q，)，qF时，则wL(M)。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例如例如，对例1给出的有限自动机M，要检查字符串101011是否被接受，我们可以写出格局的演变过程为：(q0，101011)(q1，01011)(q3，1011)(q2，011)(q0，11)(q1，1)(q0，)。由于q0F，即(q0，)是终止格局，所以101011是被例1的DFA所接受的。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 11.2.2 11.2.2 不确定的有限自动机不确定的有限自动机 不确定的有限自动机是确定的有限自动机模型的一个修改：在
20、某个输入符号的作用下，允许一个状态可以转移到某状态子集的任一状态。之所以引进NFA的概念，一方面因为理论上已经证明，任一个NFA所接受的语言L，都存在一个DFA，它所接受的语言也恰好是L；另一方面，NFA在定理证明，形式语言理论和可计算性理论中起着十分重要的作用。定义定义11.911.9 不确定的有限自动机(NFA)是一个五元组M(Q、q0、F)，其中Q、q0和F的含义同它们在DFA中的含义一样，而状态转换函数为：QP(Q)，其中P(Q)是集合Q的幂集。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例例3 3设M(q0，q1，q2，q3，q4，0，1，q0，q4
21、)是一个NFA，其中状态转换函数如表11-1给出：输入 状态 0 1 q0 q1 q2 q3 q4 q0，q3 q2 q4 q4 q0，q1 q2 q2 q4 第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 同DFA类似，我们可以模拟出NFA的运行情况，也可以用状态转换图来描述状态转换的情况。如果一个字符串w被该NFA所接受，那么在状态转换图中也表现为从初始状态q0到某个终止状态qF有一条有向链，该链上各边旁标注的字符依序组成字符串w。例如例如，对于例3的NFA，其状态转换图如图11-4所示。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-
22、26 从这个图中我们看到，从q0引出的有向边共有四条，其中标注为0的有向边有两条，一条是从q0到q3，另一条是从q0到它自身，这是因为(q0，0)q0，q3的缘故。同样，因为(q0，1)q0，q1，所以从q0引出，分别到q0和q1有一条有向边的标注为1。这是不确定的有限自动机同确定的有限自动机的状态转换图的主要区别之处。与DFA类似，我们也可以用格局推演的方式检查一个字符串是否被接受。所不同的是，对于NFA，从一个格局可以推导出多个格局。对于给定的字符串，只要有一种推演能推导致终止格局(q，)，其中qF，则该字符串就是被接受的。对于例3的NFA和字符串01001，其格局的推演情况如下：第第11
23、章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 由于在上面的格局推演中，有一个演变序列导致终止格局(q4，)，所以字符串01001是可被接受的。(q0，01001)(q0，1001)(q3，1001)(q3，1)(q0，1)(q0，01)(q1，001)(q0，001)(q3，01)(q0，)(q1，)(q4，)对于不确定的有限自动机，也可以把状态转换函数扩充为：Q P(Q)，使得(1)(q，)q；(2)(q，wa)(q，w)，a)w)(，），（qrar*第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 对扩充的状态转换函数，我们有：(q，a)
24、(q，)，a)(q，a)(q，a)。所以，我们可以用代替，也不会产生混淆。这样，就可以写出不确定的有限自动机所接受的语言的定义。设M(Q，q0，F)为一个NFA，则M所识别的语言为L(M)w|(q0，w)F。*第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定理定理11.1 11.1 设L是某个不确定的有限自动机M(Q，q0，F)所识别的语言，则存在一个确定的有限自动机M，它所识别的语言也恰好是L。证明:对于给定的NFA：M(Q，q0，F)，我们构造DFA：M(Q，q0，F)如下：QP(Q)，q0q0，Fq|qF，qQ：Q Q满足(q，a)下面我们证明：对于x，x
25、L(M)xL(M)。为此只需证明：x，(q0，x)(q0，x)。我们就x的长度用归纳法证明这一点。当|x|0，x于是(q0，)(q0，)(q0，)设|x|k，k1，(q0，x)(q0，x)成立。则当|x|k1时，我们记xwa，a，这时|w|k，于是(q0，x)(q0，wa)(q0，w)，a)，由归纳假设则有(q0，w)(q0，w)，于是有(q0，x)(q0，w)，a)。另一方面(q0，x)(q0，w)，a)。因此，对任x，有(q0，x)(q0，x)，从而证明了本定理。*qrar），（*)w0(，），（qrar)w0(，），（qrar第第11章章 形式语言与自动机简介形式语言与自动机简介 202
26、2-11-26 例例4 4 设M(q0，q1，0，1，q0，q1)，其中(q0，0)q0，q1，(q0，1)q1，(q1，0)，(q1，1)q0，q1。解 显然，M是一个NFA。我们要构造一个等价的DFA，记M(Q，0，1，q0，F)，使得L(M)L(M)。为此应取Q、q0、F如下：QP(q0，q1)，q0，q1，q0，q1q0q0Fp|pq1且pQq1，q0，q1：Q0，1Q，应有(，0)(，1)由于(q0，0)q0，q1，故有(q0，0)q0，q1。同样可得:(q0，1)q1，(q1，0)，(q1，1)q0，q1。此外(q0，q1，0)q0，q1，(q0，q1，0)q0，q1。第第11章章
27、 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定理定理11.2 设G(V，P，S)为正规文法，其中V是非终结符集，是终结符集，P是产生式的集合，S是初始符，则存在有限自动机M(Q，q0，F)，使得L(M)L(G)。定理定理11.3 对给定的有限自动机M，存在着正规文法G，使得L(G)L(M)。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 11.3 11.3 上下文无关语言与下推自动机上下文无关语言与下推自动机 与有限自动机不同的是，下推自动机是一种不确定的装置。也即，确定的下推自动机只能对应上下文无关语言的一个真子集确定的上下文无关语言，不确
28、定的下推自动机才与上下文无关语言完全对应。因此，当我们提到下推自动机时，一般是指不确定的下推自动机。上下文无关语言及下推自动机在程序设计语言中有许多重要的应用，诸如程序语言的语法定义，语法分析概念的形式化，作为编译程序中的分析手段，这些应用极大地简化了编译程序的构造。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.3.1 11.3.1 上下文无关语言上下文无关语言 对多数程序设计语言来说，其语法都可以用上下文无关文法来描述。这种描述方法不仅自然，而且大大简化了程序语言的定义。例如考虑下面一组产生式：EEE；EE*E；E(E)；Eid,这里定义的是由操作符和*所
29、确定的算术表达式，id代表操作数。非终结符只有一个E，终结符包含了、*、(、)和id。不断应用上述产生式，我们可以推导出该文法的一个句子，例如：EE*E(E)*E(E)*id(EE)*id(Eid)*id(idid)*id。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 对于上下文无关文法，句型的推导可以表示成一棵树导出树(语法树)。定义定义11.1011.10 G(V，P，S)是一个上下文无关文法，树T是G的一棵导出树，当且仅当(1)每个结点均有一个取自V 的标注。(2)根结点的标注为S。(3)分支结点的标注AV。(4)如果标注为A的结点n有从左到右k个儿子依次
30、标注为x1、x2、xk，则Ax1x2xk是P中的一个产生式。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 图11-5给出的是前面定义的算术表达式文法的一棵导出树。把图11-5中的所有叶子从左向右排列，得到的恰好是一个句子w(idid)*id，我们称此树为w的导出树。事实上，导出树恰好是句型推导的一种自然描述，关于导出树与推导之间的关系，有以下结论：定理定理11.4 11.4 G(V，P，S)是一个上下文无关文法，则：Sw文法G有一棵w的导出树。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 由于上下文无关文法产生式右端可能有多于一个
31、非终结符，在每一步推导中，先替换最左非终结符的推导称为最左推导；而相应的先替换最右非终结符的推导为最右推导。对于上下文无关文法G，若wL(G)，则w的每一个最左(右)推导唯一对应着w的一棵导出树；而对w的一棵导出树，必唯一的对应着w的一种最左(右)推导。也即，导出树导出树与最左与最左(右右)推导是一一对应的。推导是一一对应的。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.3.2 11.3.2 下推自动机下推自动机 以一个栈(下推表)作为辅助记忆设备加到有限自动机上而得到的计算模型，称为下推自动机。一个下推自动机如图11-6所示。它的输入带是一个只读输入带，有
32、限状态控制器通过一个只读输入头对其进行扫描。栈的特点是“后进先出”，有限状态控制器通过读写头与栈顶打交道。当读写头把一个字符写入栈时，该字符成为栈顶；当读写头要从栈中取出一个字符时，栈顶元素被弹出。而自顶向下的第二个元素成为栈顶。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定义定义11.1111.11下推自动机(PDA)是一个七元组，M(Q，q0，Z0，F)其中(1)Q是一个有限的状态集；(2)是有限的输入字母集；(3)是有限的下推字母表；(4)状态转换函数：Q()P(Q*)；(5)q0Q是初始状态；(6)初始符号Z0，开始时被置于栈底；(7)FQ是终止状态集
33、；第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26状态q描述M的一步动作(q，a，Z)，可作如下直观解释：1)a。当M处于状态q，读得符号a，且栈顶符号为Z时，M机可以(不确定地)进入下列m种状况之一：状态转换为pi，Z出栈，符号串i(i1，2，m)入栈，输入头右移一格。若i，则只有出栈操作，栈的深度减小。2)a。M机与输入带无关地进入任一状况，但输入头不移动，该动作称为动作。由于动作的存在，即使输入带上的字符全部被读完，M仍可 能运行；而若栈被卸空，则M就再也不能动作了。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26例例1 1 M(q
34、0，q1，q2，a，b，Z，A，B，Z，q2)是一个PDA，其中由以下各式定义：(q0，a，Z)，(q0，a，A)，(q0，a，B)(q0，b，A)，(q0，b，B)，(q1，a，A)(q1，b，B)，(q1，Z)显然这是个不确定的下推自动机，下面将看到它所接受的语言为wwr|wa，b，其中wr表示字符串w的逆转。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26定义定义11.12 11.12 M(Q，q0，Z0，F)是一个PDA，它的格局是一个三元组(q，w，)Q *，其中(1)q是有限状态控制器的当前状态；(2)w表示只读输入带上还未扫描到的那一部分字符串，w的第
35、一个字符正处于输入头的下方。若w，说明输入带上的字符已全部被扫描。(3)是下推表的内容，它的最右边的字符是当前的栈顶元素，若，则表示栈已被卸空。下推自动机M的运行，可由其格局之间的推导关系来表示，12表示由1可以推出2。如果(q，)(q，a，Z)且w ，*，则有(q，aw，Z)(q，w，)。*第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 一般来说，对于一个特定的输入字符串w，M的初始格局是(q0，w，Z0)，终止格局的定义有两种不同的方式：(1)若qF，则格局(q，)，*作为终止格局；(2)把栈空的格局(q，)，qQ，作为终止格局。从而，M所接受的语言就是两种不
36、同的定义方式：定义定义11.13 M(Q，q0，Z0，F)是一个PDA。M的以终态接受的语言记作L(M)，L(M)w|(q0，w，Z0)(p，)，pF，*。定义定义11.14 M(Q，q0，Z0，)是一个PDA。M的以空栈接受的语言记作N(M)，N(M)w|(q0，w，Z0)(p，)，pQ。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 对例例1 1中的下推自动机M，考虑输入字符串wabba，则M的格局推导式为：(q0，abba，Z)(q0，bba，AZ)(q0，ba，BAZ)(q0，a，BBAZ)(q0，ABBAZ)(q1，a，AZ)(q1，Z)(q2，)这里，
37、有一个格局推导能导致终止格局(q2，)，从而w是被M的终态所接受的字符串，wL(M)。进一步的考虑可知，M的以终态接受的语言L(M)wwr|wa，b。考虑M的以空栈接受的语言时，终止状态集是无关紧要的，常记作空集。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例例2 2 M(q0，q1，0，1，X，Z0，q0，Z0，)是一个PDA。其中可由以下各式定义：(q0，0，Z0)，(q0，0，X)，(q0，1，X)(q1，1，X)，(q1，X)，(q1，Z0)考察两个字符串w100011，w200111，由(q0，w1，z0)(q1，)，知w1N(M)。而(q0，w2，
38、Z0)(q1，1，Z0)不能导出终止格局，w2N(M)。可以证明，对于本例的PDA，N(M)0i1j|i1，1ji。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 11.3.3 11.3.3下推自动机与上下文无关语言下推自动机与上下文无关语言 对于下推自动机，用空栈接受和用终止状态接受语言的定义方法，是否存在本质上的不同呢？下面两个定理就回答了这个问题。定理定理11.511.5 对语言L，如果存在一个下推自动机M2，使LL(M2)，则必存在一个下推自动机M1，使LN(M1)。定理定理11.6 11.6 对语言L，如果存在一个下推自动机M1，使LN(M1)，则必存在
39、一个下推自动机M2，使LL(M2)。以上定理证明了PDA的两种语言定义在描述能力上是等价的。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 下面的定理指出下推自动机是与上下文无关文法对应的识别器。定理定理11.711.7 L是一个上下文无关语言存在一个下推自动机M，使得LN(M)。对于例2中的语言N(M)，我们能构造出与它对应的上下文无关文法G(S，A，0，1，P，S)，其中PS0A，A0A，A0A1，A1，从而，N(M)是一个上下文无关语言。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 由本节开始的假定知，定理11.7中的下推自动
40、机指的是不确定的下推自动机(NPDA)。DPDA即确定的下推自动机的不同之处在于，在任何格局下最多只能有一种可能的格局推导，其形式化定义如下：定义定义11.15 11.15 M(Q，q0，Z0，F)为一个确定的下推自动机(DPDA)，如果它满足：对任意的(q，a，Z)Q ，|(q，a，Z)|(q，Z)|1。可以证明，例1中的L(M)不能被任何DPDA所接受。也即 DPDA和NPDA是不等价的。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 综合以上三个定理，容易推出下面三个命题是等价的：(1)L是上下文无关语言。(2)存在下推自动机M1，使LN(M1)。(3)存在
41、下推自动机M2，使LL(M2)。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 图灵机图灵机(TM)是一种重要的计算模型，它由英国数学家是一种重要的计算模型，它由英国数学家AMTuring于于19361936年提出。这个模型很好的描述了计算过年提出。这个模型很好的描述了计算过程。无数的事实表明，任何算法都可以用一个图灵机来描述，程。无数的事实表明，任何算法都可以用一个图灵机来描述，这就是著名的丘奇论题。图灵机在可计算性理论中起着重要这就是著名的丘奇论题。图灵机在可计算性理论中起着重要作用。可以证明图灵机识别的语言就是作用。可以证明图灵机识别的语言就是0 0型语言。
42、型语言。11.4 11.4 图灵机图灵机 第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-2611.4.1 11.4.1 图灵识别器图灵识别器 图灵机的基本模型如图11-7所示。它由一个有限状态控制器，一个读写头和一个输入带组成。其中输入带具有最左端，但右端可以无限伸长。带上的每一格恰好有一个字符。开始时，带上最左边的n个格存放着由有限输入字母表上的字符组成的字符串，第n1格及其右边各格均为空白。空白是一个特殊的带符号，它不属于输入字母表。读写头一次可以在带上读或写一个字符，并可根据指令向左或向右移一格。有限状态控制器根据当前的状态，读到输入字符并发布指令。指令的内容包
43、括状态转换，在带上的一格写上(更换)字符，以及读写头向左或向右移动一格等。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 定义定义11.1611.16 图灵机(识别器)是一个七元组M(Q，q0，B，F)，其中(1)Q是一个有限状态集。(2)是输入字母表。(3)是所有允许的带符号的有限集，且。(4)：QQL，R是一个转换函数，其中L和R分别表示读写头左移或右移一格，对于某些qQ和a，(q，a)可以无定义。(5)q0Q为初始状态。(6)B是空白符。(7)FQ是终止状态集。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26定义定义11.17 1
44、1.17 图灵机M的格局记作1q2，这里qQ是M的当前状态，12*，12是输入带上从初始端(最左端)直到最右边的非空白符号为止的内容。读写头正扫视着2最左符号，若2，则读写头扫视一空白符。定义定义11.1811.18 设X1Xi1qXiXn是图灵机M的一个格局，如果(1)(q，Xi)(p，Y，L)，则若i1，则没有下一个格局；否则，X1Xi1qXiXnX1Xi2pXi1YXi1Xn；(2)(q，Xi)(p，Y，R)，则X1Xi1qXiXnX1Xi1YpXi1Xn，其中，12表示由1可以推出2。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 图灵机M对任意一个输入字
45、符串w，格局推导有三种结果：(1)进入终止格局。若q0w1p2，pF，则称1p2是终止格局，且字符串w被接受；(2)停机拒绝。若q0w1p2，且1p2没有下一个格局，则M停机。当pF时，字符串w被拒绝；(3)永不停机。即对任何可达的格局总有下一个格局。定义定义11.1911.19 设M(Q，q0，B，F)是一个图灵识别器，M所接受的所有字符串的集合称为M所识别的语言，记为L(M)。即L(M)w|w*，q0w1p2，pF，1、2*第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 例例1 1给出识别语言为L(M)0n1n|n1的图灵机M。解 识别过程如下：开始时输入带上
46、的符号序列为0n1n。M把最左的0替换成X，读写头右移到最左的1，将之替换成Y。然后左移找到最右的X，右移一格找到最左的0，重复前面的循环。如果当寻找1时M找到的却是空白，M停机拒绝；而当M把一个1替换成Y后，却再也找不到0，则检查有无剩余的1，若没有则接受。综上所述，M(Q，q0，B，F)为所求的图灵机(识别器)，其中Qq0，q1，q2，q3，q4，0，1，0，1，X，Y，B，Fq4，由表11-2给出：第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26表11-2 0 1 X Y B q0(q1，X，R)(q3，Y，R)q1(q1，0，R)(q2，Y，L)(q1，Y，
47、R)q2(q2，0，L)(q0，X，R)(q2，Y，L)q3 (q3，Y，R)(q4，B，R)q4 设输入带上的符号串w000111，考察这个图灵机的格局推导序列如下：q0000111Xq100111X0q10111X00q1111X0q20Y11Xq200Y11q2X00Y111Xq000Y11XXq10Y11XX0q1Y11XX0Yq111XX0q2YY1XXq20YY1Xq2X0YY1XXq00YY1XXXq1YY1XXXYq1Y1XXXYYq11XXXYq2YYXXXq2YYYXXq2XYYYXXXq0YYYXXXYq3YYXXXYYq3YXXXYYYq3BXXXYYYBq4由于q4F
48、，所以字符串w000111L(M)。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 因为0型文法产生的语言为递归枚举语言，下述定理说明图灵机(识别器)是与0型文法对应的识别器。定理定理11.811.8 语言L是递归枚举语言存在一个图灵机M识别L，即LL(M)。本节讨论的是基本的图灵机，此外，还有一些“加强”形式和“减弱”形式的图灵机，有趣的是，他们都与基本图灵机具有完全相同的识别能力。双向无限长输入带图灵机便是一种“加强”形式的图灵机，它与定义11.16唯一的区别便是输入带两端是无限长的。我们有如下定理：定理定理11.911.9 语言L被一个双向无限长输入带图灵机
49、所识别L被一个基本图灵机所识别。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 11.4.2 11.4.2 用于计算的图灵机用于计算的图灵机 同有限自动机一样，除了作为语言识别器，图灵机还可以对输入的信息(字符串)进行加工，并把加工的结果输出，我们称图灵机的这种功能为计算函数。用于计算的图灵机常称为五重组图灵机。其输入带是双向无限长的，输入信息放置在带中间，两端均为空白符号。这种图灵机没有终止状态集。一般地，输入字符集和带符号集是同一集合。这种图灵机的读写头的移动方式有三种。L：左移一格；R：右移一格；N：不移动。第第11章章 形式语言与自动机简介形式语言与自动机
50、简介 2022-11-26 定义定义11.20 11.20 五重组图灵机定义为M(Q，M，q0)其中(1)Q是有限状态集。(2)是读写带上的符号集合。(3)ML，R，N。(4)q0初始状态。(5)：QQM，对某些qQ，X ，(q，X)可能无定义。第第11章章 形式语言与自动机简介形式语言与自动机简介 2022-11-26 对于五重组图灵机的格局定义，完全与11.4.1类似，记作1q2，qQ，1、2，1和2是当前输入带上的非空白部分。我们只要注意到当前字符串12的两端均是无限多的空白即可。格局推导仍用连接，不同的是：当(q，X)(p，Y，L)，qXpBY(没有最左端)；而当(q，X)(p，B，R
