形式语言与自动机复习总结

1、i.i.形式语言与自动机复习总结适合形式语言与自动机 (第 2 版)、杨娟，石川，王柏主编形式语言：形式化描述的字母表上的字符串集合， 是一种公认的符号和表达式所描述的 一种语言，是通用的语言。自动机：具有离散的输入输出模型。状态：一个标识，能区分自动机在不同时刻的状况。自动机本质：根据输入和规则决定下一个状态。部分常见的自动机：有限自动机：具有读头的有限控制器和一条写有字符的输入带组成。下推自动机：由一个输入带，一个有限控制器和一个下推栈组成。图灵机：一个具有读写头的有限控制器和一条无限带组成。部分术语字母表：字符的有限集合，记为 。字符串：由字母表 中的字符构成的序列。Note: 一般字符

2、串常用 来表示，单个字符常用 来表示。字(串)：字母表 上的字符串。空串：不包含任何字符的字符串，用 表示。长度：字符串 上的字符个数，用 表示。连接：设 为串，且 ， ，那么 和 的连接定义为。性质：i.ii.iii.字符串的逆：字符串 的倒置，用 或 表示，其中 。幂运算：设 为字母表， 为任意自然数，定义：ii.设 ，则例题 2：找出由下列各组生成式产生的语言（起始符为）:例题 2：找出由下列各组生成式产生的语言（起始符为）:iii.中的元素由 i和 ii生成闭包：闭包：Note:语言：设 为字母表，则任何集合 是字母表 上的一个语言。语言的积： 和 的积表示为 ，表示由 和 的字符串连

3、接所构成的字符串的集合。集合。Note:语言的幂： 。Note: 字符串和语言的关系可以类比集合的元素和集合的关系。文法：定义语言的数学模型。列举法：表示有限集合。文化产生系统：由定义的文法规则产生语言。机器识别系统： 当一个字符串能被识别系统接受， 则这个字符串是语言的一个句子。BNF：讨论某种程序设计语言语法的元语言|定义为”,或者”, : “必须的部分”Chomsky 文法体系：将 BNF 中的“ ”用“”代替，用字符代替汉字包含两个不同的有限符号的集合：非终结符 和终结符 ，形式规则的有限集 ，起始符，文法 ， 的集合， , 。所以 一定是非空字符串直接推导：设 是文法，若 是 中的生

4、成式， 和 是 中的字 符串，则有， 称为直接推导出 ，或 是 的直接推导a）推导序列： 为 中的字符串， 且 ，由 直 接推导出 。则序列 是长度为 的推导序列， 对于 推导出 ，记为 ，若 ，记为 。b）句型：字符串 是文法 的句型 ，且 .c）句子： 是 G 的句子 ，且Chomsky 文法体系分类a）0 型文法：无限制文法，与图灵机等价。b）1 型文法（上下文有关文法） ：对于 ，有 ， 对应上下文有关语言（ CSL）与线性有界自动机等价。c）2 型文法（上下文无关文法） ： ， ，对应上下文无关语言（ CFL）与下推自动机（ PDA）等价d）3 型文法（正则文法） ：i. 右线性文法

5、：或，ii. 左线性文法：或，对应正则语言，对应有限自动机。Note: 3 型 2 型 1 型 0 型例题 1：找出右线性文法，能构成长度为1至 3个字符且以字母为首的字符串。解： ，其中如下:解： ,有限自动机：具有离散的输入，输出的数学模型（ 可以没有输出，特殊的也可以没有输入）FA 模型：一个控制器读一条纸带上的字符（包括有限状态，从左到右读字符，状态 +激 励 状态迁移）DFA：每一次转换的后继状态唯一的自动机a）定义：一个五元组b）：有限的状态集合， ：有限的字母输入字母表， ：转换函数（状态转移集合） ，：初始状态， ， ：终止状态 集， 。 可以采用状态转移图或状态转移表来表示。

6、c）函数：接收一个字符串的状态转移函数，定义： ，若 是一个字符串， 是一个字符，则对于 DFA：Note: 这里的输入均默认为合法的输入，不合法的输入暂且不考虑。格局：描述有限自动机在某一时刻的工作状态，使用 表示。 为当前状态， 为待输入字符串， 初始格局，终止格局 ，格局的转换用表示。NFA：不确定的自动机，同一情况下可以有不同的选择能力。定义：一个五元组 ，其中 是 （ 的幂集）的函数，其他与DFA 相同，同样 也可以扩展成 ，满足 ，且。定理：设一个 NFA 接受语言 ，那么必然存在一个 DFA 接受 。 采用子集构造法。例题：根据 NFA 构造 DFA，其中 如下：解：五元组 ，其

7、中 如下：14. 带 转换的 NFA ：定义：当输入空串 （无输入） 是，也能引起状态迁移的 NFA，五元组，和 NFA 区别是 。闭包：状态 的 闭包，记为 或 ，定义为从 经过所有的 路径可以到达的状态（ 包括 自身 ）。Note: 某一状态 在接受空串的时候， 表示它仍旧在这一个状态下， 因此 包 含自身状态。状态子集 的 闭包：对于状态子集 ，任意 ，定义扩展转移函数：设一个 NFA ，扩展定义Note: 在这个情况下， 和 函数有很大的区别。定理：如果 被一个具有 转移的 NFA 接受，那么 可被一个不具 转移的 NFA 接受。构造方法：设 是一个 NFA ，可以构造一个无 的 NF

8、A：。对于 （ 注意这两个函数的区别， 前者是普通的转移函数，后者是 转移函数 ）例题：对下面矩阵表示的NFA，将此 NFA 转换为没有 转换的 NFA。解：求解无 的 NFA，由于，因此，终止状态五元组其中 如下：得到的无 的 NFA 如下：正则式和正则集a）正则集：字母表上的一些特殊形式的字符串的集合，是正则式所表示的集合。（也叫做正则语言）b）正则式（集）的运算：联合（ + ），连接（ ），（星）闭包（ ）。优先级： ， 对应语言的三种运算：联合：连接：闭包： ,c）正则式：基础： 都是正则式（原子正则式），相应的正则集为 .归纳：若 和 式正则式， 且分别代表集合 和 ，则 也是正则式

9、，分别表示正则集 .d）正则式的性质：i.ii.iii.iv.v.vi.vii.viii.ix.x.xi.xii.右（左）线性文法与正则式：设 , 则 的解为Note: 这里的 就是 ，代表的是或的含义。例题：找出文法的正则式：，生成式 如下：解：由生成式可得：将 代入 中，并求解 可得：代入 和式子中，得到定理：正则集由右线性文法产生的语言，由右线性文法产生的语言都是正则集。正则语言构造右线性文法：对于联合运算 ，构造为对于连接运算 ，构造对于星闭包运算 ，构造有限自动机构造正则表达式(中间状态消去) ：a) 算法一：i. 对每一个终态 ，一次消去 和初态之外的其他状态替换为替换为替换为ii

10、. 若 ，最终可以得到一般形式 .若 ，可以得到一般形式 .最终正则表达式为每一个终态对应的表达式之和 .b) 算法二：i. 将原自动机扩展为广义的自动机 (),方法是在原自动机上增加一个新的起始状态 ，一个新的唯一终止状态 ；从新起始到老起始加一个 转移，从每个老终止到新终止状态加一个 转移。ii.递归使用过程D.设 是 的状态数如果 ，则返回从 到 上的正则式 ，结束。如果 ，从 中任取一个 、 以外的状态 ，并且令 为，其中 ，对每个 ， ，消去其间的 状态使 ，其中：，计算 ，且返回这个值24. 从正则表达式构造等价的 NFA对于 ，构造为对于 ，构造为：对于 ，构造为c)d)对于 ，

11、构造为：e)对于 ，构造为：f) 对于 ，构造为：定理：有限自动机 右线性文法a) 从右线性文法构造有限自动机：设右线性文法 ，构造一个与 等价 的优先自动机 NFA ，其中： ， 为新增加的一个状 态， ，的定义为：当 ，则当 ，则对于任意输入， 。b) 从有限自动机构造右线性文法： 设有限自动机 ，构造一个右线性文法 ，其中 ， 的定义为：若 且 ，则 在 中若 且 ，则 和 在 中例题 1：设右线性文法，其中生成式 如下：构造 NFA 。解：构造 NFA，其中：定义如下：当，则有；当 ，则有 ；当，则有；且。例题 2：设有 DFA，其中转换函数如图所示，试构造与之等价的右线性文法 。q解

12、：构造右线性文法产生式集合 :由于 是终止状态，所以，化简 得到：例题 3：设正则集为(1) 构造右线性文法；(2) 找出 (1)中文法的有限自动机。解：( 1) .此正则式含义为交替连接，最后以 结尾。那么，右线性文法为 ，其中 为或者分解正则式， ，其中 为(2).有限自动机为定义为：DFA 极小化：对于一个 DFA 的极小化，即找出一个状态数比 M 少的 DFA 满足a) 等价： 设 DFA ，对不同的状态 ， 和每个 ，如果有 必有 且 ，则称 与 状态等价，记为，否则，称 ， 可区分。b) 不可达状态：如果不存在任何 ，使 ，则称状态 为不可 达状态 .最小化：若 DFA 不存在互为

13、等价状态及不可达状态，则称 DFA 是最小化的最小化算法：a) 算法一：构成基本划分， ( 为终态集， 为非终态集 )；ii.细分 。当输入任意字符 时，若 中的状态经过 的边可到达的状态集的元素分属于两个不同的子集中，则将 细分 为两个子集；iii. 重复步骤 ii，直至不可再细分， 得到 。若 中有不可达状态， 将其删除， 便是最小化的。b) 算法二：基础：假设 为终态， 为非终态，则 和 标记为可区分的。归纳：设 和 是已经标记为可区分的，若状态 和 通过输入符号 ，满足，则 和 也标记为可区分的。重复步骤 ii ，合并等价的状态。例题：已知 DFA 的状态转移表如下，构造最小状态的等价

14、 DFA解：这里根据状态转移表可知，状态 属于不可达状态，故删掉不考虑。接下来使用填 表法求解最小化 DFA，其中， 是起始状态， 是终止状态。可以知道 是等价的，所以得到最小 DFA其中Pumping 引理（正则语言的一个必要条件） ：a） 定理：设 是正则集，存在常数 ，对于字符串 且 ，则 可以写成，其中 ，对于所有的 ，有 。b） 应用：证明一个式子不是正则式， 选取任意一个 ，找到一个长度至少为 的串 TOC o 1-5 h z ，任选满足 的 ，找到一个（ 尤其是），使得例题：使用泵浦引理，证明下列集合不是正则集（1 ）由文法 的生成式 产生的语言 ;（2 ）;（3 ）。解：（ 1

15、） .假设该文法可以产生正则集，由文法可知，取足够大的，并取串 ，要满足 pumping 引理，那么一定有 ，且 。而 ，所以，这里 的 一定为 。那么我们应当有 ， 即 ，仅当 时才成立，所以，与文法矛盾。故不是正则集。（ 2） .假设该集合是正则集，那么对于足够大的，串 ，那么根据pumping 引理， 一定有，且 。而 ，这里取 ， 。那么一定存在 ，取 ，此时 ，和要求的 矛 盾，故 不属于集合，从而该集合不是正则集。3 ).假设该集合是正则集， 串，那么根据 pumping 引理，一定有 ， 且 。而 ，这里 取 ， ，那么一 定存在，取 ，此时 ，与集合的形式矛盾，故该集 合不是正

16、则集。右线性语言的封闭性：设 和 是右线性语言则 均是右线性语言。a) 构造 : 其中：是一个新状态， ， ，定义为：当 ，则 ；当 ，则 ；当 ，则 ；对任意 ， 。b) 构造 ： 其中对于则双向有限自动机： 读入一个字符后， 读头可以左移一格， 也可以右移一格， 或者不移动， 而确定的有限自动机必须向左或者向右移动。形式化定义： ， 为 的映射。或 ， 表示左移和右移如果使用格局表示，则为例题：设 2DFA ，其中转换函数 如下：当输入字符串 时，其格局序列为因 是终止状态，所以字符串 是可被 所接受的。米兰机：: 其中 为有限状态集合， 为有限输入字母表， 为有限输出字母表， 为转换函数

17、， 输出函数， 为初始状态，摩尔机：: 其中 为有限状态集合， 为有限输入字母表， 为有限输出字母表， 为转换函数， 输出函数， 为初始状态，米兰机和摩尔机的转换：a) 摩尔机 米兰机：摩尔机 中有 ，则米兰机;b) 米兰机 摩尔机：每一个状态 ，如果它的输出相同，则复制状态 ；如果某状态 有 个不同的输出，则将它分割成 个状态；如果初始状态输出为 0，则插入一个新的状态，并给出一个输出。 Test:(有限自动机均使用状态图表示)一、（15 分） 设 ，给出下列语言的文法并指明它是几型文 法。（ 1） 的串中 的个数为偶数（2）（1）.可以先使用有限自动机，或者先用正则式表示。这里就采用有 限

18、自动机：那么构造的文法就是属于 3 型文法。（ 2）.本题关键是，我们可以先考虑 ，那么这个文法就有如果想保证不相等，也就是 的个数大于 或者 的个数大于那么 可以写作 ， 可以写作 因为我们至少要保证一个字符的个数多，所以可以让 终结于一个非 终结符。所以文法就是：属于 2 型文法。二、（20 分） 给出下述语言的正则式和自动机。（ 1）至少含两个 ，至多一个（2）中串的最后一个符号在前面出现过。（1）.由于正则式和自动机是等价的，所以我们可以先构造自动机，满足至少两个 和至多一个 。所以，可以使用状态消去法得到正则式：(2).同样，先画出有限自动机然后给出正则式：三、(20 分) 已知带

19、的 NFA 如下图所示 , 求其等价的 NFA，DFA首先，先求出它的 NFA ，由于，因此 NFA中，终止状态集 。接下来计算转移函数接下来使用子集构造法，四、（15 分） 用填表法对下图的自动机化简首先，没有不可达状态，接下来使用填表法所以， , , 不可区分。五、（15 分） 证明语言是二进制串 不是正则集。采用 pumpling 引理，假设该语言是正则集，假设一个语言串为，并且 ，符合语言 的特性。那么 ，由于 ，所以， 一定是 ，那么对于任意的 ，如果，一定不可能存在 ，这和 pumpling 引理矛盾，故，语言 不是正则集。六、（15 分 ） 构造米兰机或摩尔机，输入为上的字符串，

20、当输入一个三进制数（基数为 3，数字为 0，1， 2）时，输出为输入 模 4 的余数。要求给出简单分析并画出状态转换图 . 对于一个字符串而言，输出模 4 的余数，那么我们就需要 4 个状态， 分别代表模 4 的 4 个余数 0，1， 2， 3。对于一个已有的数字而言，我们可以使用 来表示每当多一个字符以后， 这些数字都分别乘以 3，得到一个新的数，加上新的数字，从而可以得到余数的关系。那么，状态转移关系如下：采用摩尔机34. 归约与推导：推理字符串是否属于文法所定义的语言。 a） 归约：自下而上的推理方法，也称为递归推理。 b） 推导：自上而下的推理方法。 归纳过程：将产生式右部替换为产生式

21、的左部。 推导过程：将产生式的左部替换为产生式的右部。最左推导：推导的每一步总是替换出现在最左边的非终结符，最左推导关系：最右推导：推导的每一步总是替换出现在最右边的非终结符，最右推到关系：推导树：用图的方法表示一个句型的推导， 定义：文法的起始符为根，树的枝结点标记为非终结符，叶结点标记为终结符或若枝节点有直接子孙 ，则文法中有生成式 边缘：叶子从左到右组成的的字符串称为推导树的边缘。归约，推导和推导树之间的关系： （设 CFG（上下文无关文法），则以下说法等价）a）字符串 可以归约到非终结符b)c)d）e）存在一个根节点为 的推导树，边缘为 。二义性： 2 行文法是二义的 对于句子 ，存在

22、两棵不同的具有边缘为 的推导 树。Note: 存在这样情况，有两个文法，一个没有二义性，一个有二义性，但产生相同的语 言。生成式的标准形式：a）Chomsky 范式（ CNF）：生成式的形式为b）Greibach 范式（ GNF）：生成式，意义为对每个 2 型语言，都可以找到一个文法，是产生式的右端都以终结符开始。有用符号：对于 CFG，称 是有用的 ，其中a）是生成符号 满足 ;b）是可达符号 满足不属于以上两者的称为无用符号计算生成符号集：对于 CFG，通过以下归纳步骤计算：基础：任何终结符 都是生成符号。归纳：如果有产生式 ，其中 的每一个符号都是生成符号，则 也是生 成符号。算法：，

23、为有用的非终结符；， 为非终结符集， ；若 ，转 d)，否则转 f) ；，转 c)；.计算可达符号集，对于 CFG，算法：；( 为有用符号集合) , ， ；若，转 d)，否则转 e)；转 b) ；， ， 由 内只含 中符号生成式组成。Note: 在消去无用符号的过程中，上面的两步一定要按照顺序先计算生成符号，然后再计算 可达符号。例题：将文法改变成没有无用符号，等价的上下文无关文法：解：根据生成符号的判断算法，我们可以得到 是生成符号，因此删掉 和。接下来运用可达符号的判断算法，我们可以得到 均为可达符号所以，删除 以及 得到等价的文法的表达式为：可致空符号：对于 CFG，称符号 是可致空的，

24、当且仅当 。生成无 文法：定义：若 的生成式中无任何 形式，或只有一个生成式 且 不出现在任何生 成式的右边，称 为无 文法。计算生成符号集合：对于所有产生式 ， 是一个可致空符号； 如果由产生式 ，其中每一个 是可致空符号，则 是一个可致空 符号。生成无 文法：找出生成 的符号集合 ；若生成式 且每个 均在 内，而对于 ，没有 在 内( 也可能是终结符) ；则集合 应加入 的所有可能组合，其中 或是 或是 ，但 不 加入 ；若 ，则 中加入生成式 ， 是新起始符， 。若 ，则 。得到新的文法：例题：将下面的文法变成无 文法：解：由于存在 ，故而存在 ，所以，存在 ，故存在 ， ，故存在 ，故

25、，存在 , 所以 。构成新的生成式集合进行不同的组合得到由于 ，所以，需要添加一个生成式：故得到新的 :从而得到新的文法：消去单产生式：单产生式：形如 的产生式，其中 为非终结符。单元偶对：对于 CFG， ，称 是单元偶对，当且仅当。消去单产生式：对每个，构造非终结符集 。若且不是单产生式，则对于的所有 ，把 加入到 中，。得到 。例题：将下面的文法变成无 生成式、无单生成式和没有无用符号的等价文法：解：先消除 ，首先，由于 ，且 ，所以集合 。根据生成式 ，得到 ，从而集合根据生成式 ，得到 ，从而集合 根据生成式 ，得到 ，从而集合那么我们得到由于 ，所以生成式集合 ：得到的新文法消除单产

26、生式：那么得到的新生成式集合 ：从而得到新的文法消除无用符号：这些集合中的符号均为生成符号但除了 外均为不可达符号，所以均为无用符号因此，得到的新文法生成式代换：定义： 2 行文法中，所有形如的生成式称为 的生成式引理：对于 的 生成式可以进行变换设 ， 是 中的生成式，是 中的 生成式，可生成中的生成式是将 中的 用消除直接左递归：设 ， 中有 生成式， ，其中 的第一个字符不是非终结符 (可以是其他的终结符) 。可构成新的文法为新引入的非终结符， 中的 为 中 生成式用如下生成式取代：消除所有的左递归：排列所有的非终结符 ，设置将 变为，若 ，继续 d)， 否则转 f)对每个 ， ，用 代

27、替若 转 b)，否则转 d) ，若，结束。例题：消除下面文法的左递归：解：先排序： 对于产生式，不需要变动 ;对于产生式：进行变换消直接左递归：对于产生式：进行变换首先代入变为 其次：直接消除左递归：Chomsky 范式( CNF)：每个上下文无关文法都具有等效的CNF。算法：a) 先消 生成式，无用符号，单产生式。b) 对生成式 ，若，则引入新生成式 ， 是新的非终结符，若 ，令 ，从而生成当 是，再将其变为 ， 是 新的非终结符。例题：设 2 型文法 ，其中，试将 变换为无 生成式，无单产生式，没有无用符号的文法，再将其转换为 Chomsky 范式解：先消 ，这里直接生成 的符号包括 ，

28、而 是起始符，所以需要添加一个生成式：那么得到新的 为：那么新的文法下面消除单生成式：可以得到 ， ， ， 因此，得到新的 ：新的文法为：继续消无用符号：生成符号为：可达符号为：因此并没有无用符号，所以继续保持文法 接下来求 Chomsky 范式： 令 从而得到新的生成式 ：所以得到的文法Greibach 范式：任何 2 型文法都具有等效的 GNF 算法：将 2 型文法变为 CNF将非终结符排序代换， 对于形如 的生成式代换， 直至消左递归回代：将 生成式回代入 生成式使其右部首个字符为终结符。将 生成式回代入 生成式，依次进行，最后把 生成式右部代换， 使得首个字符为终结符。下推自动机( P

29、DA)：定义：七元组其中， 为有限控制器状态的集合， 为有限输入字母表， 为有限下推栈字母表，为转移函数，为起始状态， ， 为下推栈的起始符号， ， 为终态集合，Note ： .，表示在状态 ，输入 ，且栈顶符为 时，转入状态 ，栈顶符号由 代替，同时读头右移一格。. 约定， 的最左符号放在栈顶。设 CFG，构造一个空栈接收方式的 PDA.表示下推栈的栈顶符号被弹出。. 下推自动机接受的语言包括终态语言和空栈语言，这两种接受方式是等价的。 例题：构造识别该语言的 PDA，.设 PDA那么需要保证 1 的个数不少于 0 的， 所以可以设一个下推自动机，下推栈中保存1，在栈变为空栈时必须终止，或者

30、在空栈之前终止。所以，得到下推自动机：从而可知 PDA其中 如下：确定的下推自动机（ DPDA ）：对于 ，满足下面两个条件之一a） 最多含一个后续选择且 。b） 且 最多含一个元素。 如果不满足，就是非确定的下推自动机（ NPDA ）。定理：上下文无关文法（ CFG） 下推自动机（ PDA）由 CFG 导出 PDA：其中 , , , ; 转移函数 定义为： 对于每一个,对于每一个,例题：构造与下列文法等价的 PDA ：（1）（2）解：（ 1）、构造新的 PDA其中 的定义为：（2 ）、构造新的 PDA其中 的定义为：非终结符 ， ，含义为在 状态时，栈顶为 时，接收某个字符(可以 是 )后 PDA 将变换到 状态。 代表当前状态是 ，栈顶符号是 ，接受字符 串 后的状态是 。从下推自动机构造等价的上下文无关文法：设 PDA ，构造 CFG其