第二章 词法分析 词法记号及属性 词法记号的描述与识别 有限自动机 DFA构建 DFA化简 词法模式的识别过程 子集构造法.

Presentation on theme: "第二章 词法分析 词法记号及属性 词法记号的描述与识别 有限自动机 DFA构建 DFA化简 词法模式的识别过程 子集构造法."— Presentation transcript:

1 第二章 词法分析 词法记号及属性 词法记号的描述与识别 有限自动机 DFA构建 DFA化简 词法模式的识别过程 子集构造法

2 编译过程 源程序 词法分析器 语法分析器 语义分析器 符号表管理器 出错管理器 中间代码生成器 代码优化器 代码生成器 目标程序

3 词法分析器的功能 词法分析器 记号（token）流 源代码

4 第二章 词法分析 记号 源程序 词法分析器 语法分析器 取下一个记号 符号表 本章内容
第二章 词法分析 词法分析器 语法分析器 符号表 记号 取下一个记号 源程序 本章内容 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务。 介绍正规式、状态转换图和有限自动机概念。 Lex与词法分析器的自动生成。 围绕词法分析器的自动生成展开

5 本讲内容 词法记号及属性 01 词法记号 02 词法模式 03 词法单元 04 词法记号的属性 05 词法错误

6 词法分析：编译第一步 看一个中文的句子 你们 是 优秀的 大工学子 代词 动词 形容词 名词（短语）
通过分词操作，把句子以单词或者词组为单位进行划分，得到一个句型。

7 C语言的语句例子 词法单元 词法记号 例子中 哪些是词法单元？ L1 : x = y2 + 12 ; ID COLON ID ASSGN
又称单词，是编程语言中合法的字符串 词法记号 满足某种规则的词法单元，采用同一种记法。 例子中 哪些是词法单元？ L1 : x = y2 + 12 ; ID COLON ID ASSGN ID PLUS INT SEMI-COL 编译的词法分析做的工作类似于分词， 把原始的字符串流形式的程序文本转换为词法记号流的形式。

8 词法单元与词法记号 满足一个给定规则的词法单元，被记为一个词法记号。 模式 词法单元 词法记号

9 词法模式 C语言的标识符 ? x2, 12, _12, _abc 哪些是合法的C标识符？ C语言标识符的规则（模式）：
首字符必须是_或者字母，由_、字母或数字组成的字符串

10 词法模式 常见记号及模式的例子： 简单的一对一模式 词法记号 词法单元例举 模式的非形式描述 STRUCT struct struct FOR for for RELOP < , < = , = , ID sum, _12, _x NUM 3.1, 10, 2.8e12 LITERAL “seg. error” < 或<= 或 = 或 … _或字母开头的由_、字母和数字组成的串 任何数值常数 引号“和”之间的任意字符串，但引号本身除外 相对复杂一点的模式

11 词法记号、模式、词法单元 名词 大连 软件 大黑山 表示名称的词 连词 和 与 或 和 与 或 ….
名词 大连 软件 大黑山 表示名称的词 连词 和 与 或 和 与 或 …. 词法记号 词法单元例举 模式的非形式化描述 词法记号 词法单元例举 模式的非形式描述 relation < , < = , = , … < 或 <= 或 = 或 … id sum, count, D5 由字母开头的字母数字串 词法记号 词法单元例举 模式的非形式描述 中国人 胡锦涛 毛泽东 具有中国国籍的人 美国人 奥巴马 克林顿 具有美国国籍的人

12 符号表的作用 词法分析器 语法分析器 符号表 记号 取下一个记号 源程序 存在的意义？

13 词法记号的属性 如果简单地把词法记号流传给语法分析器，会产生什么后果？ 语义被完全摒弃，只剩下一个语法结构。 翻译官 我是学生
Pronoun Verb Noun 说了什么呀？？？？ 你说了一句“我是学生”，翻译官翻译说 pronoun verb noun

14 词法记号的属性 每个词法记号具有一定的含义（属性） 第一个ID，名称是L1, 表示的是标号（Label）
: x = ID COLON ASSGN y2 + 12 ; PLUS INT SEMI-COL 第一个ID，名称是L1, 表示的是标号（Label） 第二个ID，名称是x, 表示的是一个变量，类型是int 第三个ID，名称是y2, 表示的是一个变量，类型是int

15 词法记号的属性 position := initial + rate * 60的记号和属性值： id，指向符号表中position条目的指针 assign _ op  id，指向符号表中initial条目的指针 add_op  id，指向符号表中rate条目的指针 mul_ op  num，整数值60

16 词法错误 词法分析器对源程序采取非常局部的观点,难以发现下面的错误： fi (a == f (x) ) …
例外：如在实数是a.b格式下，可以发现下面的错误 123. 但是也有例外，如在实数是a.b格式下，可以发现下面的错误

17 词法错误 词法错误的处理方法 恢复策略 “紧急方式” 错误修补尝试 删除一个多余的字符 插入一个遗漏的字符
用一个正确的字符代替一个不正确的字符 交换两个相邻的字符

18 小结 词法分析器工作原理： 源程序字符流 顺序组合 词法单元 词法记号 模式 非形式化描述 形式化描述 正规式 字母 组合 串 语言 集合
字母表 名字 词法分析器 记号（token）流 源代码

19 本讲纲要 词法记号的描述与识别 01 串和语言

20 词法记号的描述与识别 词法模式的表示方法，是词法记号描述的核心 下面是用于描述词法记号的模式语言。 模式 词法单元 记号

21 串和语言 字母表：符号的有限集合， 例： = {0,1} 串：符号的有穷序列，例：0110,  语言：字母表上的一个串集
串：符号的有穷序列，例：0110,  语言：字母表上的一个串集 {,0,00,000,…}, {},  长度为0的空串 长度的表示|a| 字母表 集合 组合 集合 字母 串 语言 Ε ε epsilon 艾普西隆

22 串和语言 串的运算 连接 xy s = s = s 积（指数） s0为，si为si-1s（i>0）

23 串和语言 L =L0 ∪ L+ 语言的运算 和：L∪M = {s | s L 或 s  M }
连接：LM = {st | s  L 且 t  M} 指数：L0是{ }，Li是Li -1L 闭包：L = L0 ∪ L1 ∪ L2 ∪… 正闭包： L+ = L1 ∪ L2 ∪… 例2.2（p17） L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 } L∪D, LD, L6, L*, L(L∪D )*, D+ L =L0 ∪ L+

24 小结 词法分析器工作原理： 源程序字符流 顺序组合 词法单元 词法记号 模式 非形式化描述 形式化描述 正规式 字母 组合 串 语言 集合
字母表 名字 词法分析器 记号（token）流 源代码

25 本讲纲要 词法记号的描述与识别 01 正规式 02 正规定义

26 正规式 正规式：又称正则表达式， Regular Expression
正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式 r 表示一个语言 L(r)。 定义规则说明 L(r) 是怎样以各种方式从 r 的子正规式所表示的语言组合而成。 正规式用来表示简单的语言，叫做正规集。 正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确。

27 正规式 定义字母表上正规式的规则 正规式 定义的语言 备注  {} a {a} a  
正规式 定义的语言 备注  {} a {a} a   (r) | (s) L(r)∪L(s) r 和s是正规式 (r)(s) L(r)L(s) r 和s是正规式 (r)* (L(r))* r 是正规式 (r) L(r) r 是正规式 运算符的优先级： * > 连接运算 > | ((a) (b)*)| (c)可以写成ab*| c 定义字母表上正规式的规则

28 正规式 正规式的例子  = {a, b} 复杂的例子 a | b {a, b}
(a | b) (a | b ) {aa, ab, ba, bb} aa | ab | ba | bb {aa, ab, ba, bb} a* 由字母a 构成的所有串集 (a | b)* 由a 和b 构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11)  (01 | 10) ) )  句子：

29 保证：每个名字对应的正规式中使用的各种符号已经在前面定义了，从而可以避免递归定义的情况。
正规定义 对正规式命名，使表示简洁。 d1  r1 d2  r2 . . . dn  rn 各个di的名字都不同 每个ri都是 {d1, d2, …, di-1 }上的正规式 保证：每个名字对应的正规式中使用的各种符号已经在前面定义了，从而可以避免递归定义的情况。

30 Pascal里面的标识符模式 正规式表示 letter  A | B | … | Z | a | b | … | z
digit  0 | 1 | … | 9 id  letter(letter|digit)* 怎么用语言来描述Pascal的标识符模式？ Pascal标识符模式的自然语言描述： 首字符必须是字母，由字母或数字组成的字符串。

31 C语言的标识符模式 模式的非形式描述 首字符必须是_或者字母，由_、字母或数字组成的字符串。
请仿照Pascal标识符的例子，写出C语言的标识符的正规式表示

32 letter_  A | B | … | Z | a | b | … | z | _
C语言的标识符模式 正规定义的例子 C语言的标识符是字母、数字和下划线组成的串。 letter_  A | B | … | Z | a | b | … | z | _ digit  0 | 1 | … | 9 id  letter_(letter_ |digit)*

33 正规定义的例子 Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6 digit  0 | 1 | … | 9 digits  digit digit* optional_fraction  .digits| optional_exponent  (E ( + |  |  ) digits ) |  numdigits optional_fraction optional_exponent 简化表示 num  digit+ (.digit+)? (E(+|)? digit+)? 简化规则： r+=rr* r?=r|  [a-z]=a|b|c|…|z

34 正规定义的例子 while  while do  do
relop  < | < = | = | < > | > | > = id  letter (letter | digit )* numdigit+ (.digit+)? (E (+ | )? digit+)? delim  blank | tab | newline ws  delim+ 前面所提到的词法记号，实际上就是正规式的名字！

35 本讲纲要 词法记号的描述与识别 01 状态转换图

36 词法记号的识别 词法记号的识别 等同于对字符串的匹配过程 这个匹配过程可以基于状态转换图来完成 状态转换图==有限状态机

37 状态转换图 简单的正规式d->a 正规式d->ab 正规式d->a|b a 1 a b 1 2 a 1 b

38 状态转换图 正规式d->a* 正规式d->a? 字符a出现一次或者0次 正规式d->a(a|b)* a a 1 a a 1
a 1 a a 1 b

39 状态转换图 关系算符的转换图 relop  < | < = | = | < > | > | > =
5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始 < = > * other *表示指针必须回退的状态

40 状态转换图 id  letter (letter | digit )* 标识符和关键字的转换图 9 10 开始 letter other
11 开始 letter other * letter或digit return(install_id( )) 1、检查关键字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向2 2、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行3 3、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针

41 状态转换图 num  digit+ (.digit+)? (E (+ | )? digit+)? 无符号数的转换图 digit
19 12 13 14 15 16 17 18 digit other . E +/ return(install_num( ) ) * 开始

42 状态转换图 delim  blank | tab | newline ws  delim+ 21 开始 delim other * 20
空白的转换图 delim  blank | tab | newline ws  delim+ 21 22 开始 delim other * 20 无return

43 小结 ？ 正规式 状态转换图 计算机实现 等价 有限自动机 不确定有限自动机 确定有限自动机

44 如: I love Dalian and I love DLUT
叙述正规式描述的语言（2.3题） 练习题：要求使用伪代码给出算法 编写一个程序，用于统计文件中单词的总数，不同单词的数目。（假设输入文件中只包含字母和空格） 如: I love Dalian and I love DLUT Word number：7 Distinct word number：5 每周3交作业 2018/11/24

45 本讲纲要 01 有限自动机定义 02 DFA 03 NFA 04 DFA与NFA的区别 05 状态转移表

46 有限自动机 识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。 状态转换图（有限自动机）识别器
确定/不确定有限自动机——时空权衡问题 确定有限自动机：快，空间大

47 DFA a 1 确定的有限自动机（简称DFA） 数学形式定义 DFA是这样一个数学模型，包括 状态集合S 输入字母表
转换函数 move: S    S 唯一的初态s S 终态集合F  S a 1 Nondeterministic finite automata, DFA

48 问题 请构造(a|b)*ab 的DFA ? 这个，基本上很难！ 怎么办？ 下面，先引入一个新概念…

49 2、一个状态对于某个字符，可能有多条输出边
NFA 不确定的有限自动机（简称NFA） 数学形式定义 NFA是这样一个数学模型，包括 状态集合S 输入字母表 转换函数 move: S  ({})  P(S) 唯一的初态s S 终态集合F  S 缺点：1、输入字符包括  2、一个状态对于某个字符，可能有多条输出边 P(S) S的幂集

50 NFA 例 识别aa*|bb*的NFA 1 2 开始 a b 3 4 

51 NFA (a|b)*ab的NFA (a|b)*ab的DFA 1 2 开始 a b 1 2 开始 a b

52 DFA与NFA的区别 1.NFA中允许转换边，而DFA中不允许
2.NFA中move(s,a)可能是一个多元集合，而DFA中move(s,a)最多有一个元素

53 缺点：字母表过大或大部分转换状态为空集时浪费空间
状态转移表 (a|b)*ab 状态迁移动作，从开始状态到目标状态 输 入 符 号 a b {0, 1} {0} 1  {2} 2 输 入 符 号 a b {1} {0} 1 {2} 2 优点：快速定位 缺点：字母表过大或大部分转换状态为空集时浪费空间 1 2 开始 a b 1 2 开始 a b

54 DFA or NFA 在机器上实现字符串识别过程 基于DFA? 还是基于NFA? NFA更贴近于人们对正规式的认识
DFA因为每次状态转换都是确定性的，即从当前 状态s与当前字符a，可以转换到唯一的目标状 态s’。

55 本讲纲要 1 2 3 DFA构建 途径1： 自然语言描述=>DFA 途径2： 正规式=>DFA 途径3：
正规式=>NFA=>DFA

56 DFA构建方法1 直接从自然语言描述，进行DFA的构建。 适合场景：从自然语言描述不能够得到一个简单的正规式。

57 《编译原理习题精选》1.5题。 号外：从语言到确定的有 限 自 动 机 例：识别 ={0,1}上能被能5整除的二进制数 方法：
1、列出全部可能的状态 2、从各个状态出发，构造边及输入字符记号 1 2 3 开始 4 《编译原理习题精选》1.5题。

58 号外：从语言到确定的有 限 自 动 机 例：识别 ={0,1}上能被能5整除的二进制数 1 1 1 2 3 4 开始 1 1 1

59 途径1：自然语言描述=>DFA 构建识别能被5整除的二进制数的DFA。 练习题：构建识别下列描述DFA。 偶数个0，偶数个1的01串
C语言的注释 /* … */ 作为课后思考题，课后可以把解题过程以及答案发到我的邮箱， 会作为最终平时成绩的一个参考，

60 本讲纲要 1 2 3 DFA构建 途径1： 自然语言描述=>DFA 途径2： 正规式=>DFA 途径3：
正规式=>NFA=>DFA

61 途径2: 正则表达式=>DFA 顾名思义，就是从词法模式的正规式表 示，直接得到能够识别相应模式的DFA。

62 示例1: 关系运算符的识别 正则式 relop  < | < = | = | < > | > | > = = 2 return(relop, LE) 1 > < 3 return(relop, NE) other * 开始 4 return(relop, LT) = 5 return(relop, LT) > = 7 return(relop, GE) 6 * other 8 return(relop, GT)

63 示例2: Pascal标识符的识别 正规式id  letter (letter | digit )* Letter或digit 开始
other 9 10 11

64 状态转换图 无符号数的转换图 num  digit+ (.digit+)? (E (+ | )? digit+)? digit
19 12 13 14 15 16 17 18 digit other . E +/ return(install_num( ) ) * 开始

65 状态转换图 空白的转换图 delim  blank | tab | newline ws  delim+ 21 开始 delim
22 开始 delim other * 20 无return

66 本讲纲要 1 2 3 DFA构建 途径1： 自然语言描述=>DFA 途径2： 正规式=>DFA 途径3：
正规式=>NFA=>DFA

67 途径3：正规式=>NFA=>DFA
三大步骤： 1. NFA构建 2. NFA -> DFA的转化 3. DFA化简 先构造NFA，再将NFA转换为DFA 途径3

68 正规式=>DFA? 从正规式(a|b)*ab 的自动机构造讲起。 状态0，1，2的含义并不太容易说明白。 1 2 开始 a b

69 从正规式到NFA 1 4 2 3 5 按照正规式的构建规则，逐步从简单到复杂地讨论从正规式构建NFA的过程。 单个符号 闭包 选择 连接
括号

70 从正规式到有限自动机 首先构造识别和字母表中一个符号的NFA。 i 开始  识别正规式的NFA a f 识别正规式a的NFA

71 从正规式到有限自动机 构造识别主算符为选择的正规式的NFA。  f i 开始 识别正规式s |t 的NFA N (s) N (t)

72 从正规式到有限自动机 构造识别主算符为连接的正规式的NFA。 i N (s) f 开始 识别正规式st 的NFA N (t)

73 从正规式到有限自动机 构造识别主算符为闭包的正规式的NFA。 N (s) f 开始 识别正规式s* 的NFA i 

74 从正规式到有限自动机 对于加括号的正规式(s)， 使用N(s)本身作为它的NFA。

75 下面来看一看正规式(a|b)*ab的分解动作
构建实例 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b (a|b)*ab的分解 r9 r8 b r7 r6 a r5 * r4 ) ( r3 | r1 a r2 b 1 9 开始  a b 6 7 8 2 3 4 5  7 a 2 3 6  1  a 8 9 b b 4 5 下面来看一看正规式(a|b)*ab的分解动作

76 小结 计算机实现 正规式 状态转换图 不确定有限自动机 确定有限自动机 最简确定有限自动机 确定有限自动机 语言
等价 用正规式语法结构来指导构造过程 等价 子集构造法 合并不可区别状态 不确定有限自动机 确定有限自动机 最简确定有限自动机 状态列举法 确定有限自动机 语言

77 本讲纲要 01 子集构造法

78 (a|b)*ab => NFA 1 9 开始  a b 6 7 8 2 3 4 5

79 NFA=>DFA 理论依据 怎样进行NFA到DFA的转化
根据有限自动机理论，设L为一个有不确定的有限自动机接受的集合，则存在一个接受L的确定的有限自动机 怎样进行NFA到DFA的转化 子集构造法

80 NFA=>DFA 开始 a 1 2 b 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an 后，
NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} 识别语言(a|b)*ab 的DFA 1 2 a 开始 b

81 NFA=>DFA a a b b a b 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an 后，
NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} a a {0} {0, 1} 1 2 a 开始 b b b a b {0, 2}

82 有限自动机 A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9} 状态 输入符号 a b A B C B B D C B C 1 9 开始  a b 6 7 8 2 3 4 5 D B C

83 从转换表构造转换图。 有限自动机 状态 输入符号 a b A B C B B D C B C D B C B D 开始 a A b C 1
9 开始  a b 6 7 8 2 3 4 5 D B C 从转换表构造转换图。

84 本讲纲要 1 2 3 DFA构建 途径1： 自然语言描述=>DFA 途径2： 正规式=>DFA 途径3：
正规式=>NFA=>DFA

85 途径3：正规式=>NFA=>DFA
先构造NFA，再将NFA转换为DFA 三大步骤： 1. NFA构建 2. NFA -> DFA的转化 3. DFA化简

86 DFA的化简 通过算法构造的NFA，而后经过子集构造法得来的DFA通常不是最简的 如何判定一个DFA是不是最简

87 DFA的化简 判断依据：状态的可区分性 状态的可区分性
存在串w，使得从状态s开始，对w进行状态 转换，最终停在某个接受状态；而对于从t 开始对w进行状态转换后，却停在某个非接 受状态。

88 DFA的化简 可区别的状态 A和B是可区别的状态 A和C是不可区别的状态 B D 开始 a A b C

89 DFA的化简 DFA化简的途径 根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的。 依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系。

90 DFA的化简 化简时，DFA的状态转换函数必须是一个全函数 死状态 左图无须加死状态，右图加入死状态E C a, b 开始 a b C E

91 DFA的化简 方法 1. {A, B, C}, {D} b 开始 a move({A, B, C}, a} = {B} 1 2
b 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} B D 开始 a A b C

92 小结 计算机实现 正规式 状态转换图 不确定有限自动机 确定有限自动机 最简确定有限自动机 确定有限自动机 语言
用正规式语法结构来指导构造过程 等价 等价 子集构造法 合并不可区别状态 不确定有限自动机 确定有限自动机 最简确定有限自动机 状态列举法 确定有限自动机 语言

93 本讲纲要 01 词法模式识别过程

94 词法模式识别过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) 1 2 开始 a b 状态序列：0

95 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) b 开始 a 1 2
b m(0,1) 是move(0,a)的简写， move(0,a)=1 表示从状态0，通过字母a驱动，到达的后继状态是1

96 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
2 开始 a b 状态序列：0 1

97 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) 1 2 开始 a b

98 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) = m(2,ab) 1 2 开始 a b 状态序列：0 1 2

99 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) = m(2,ab) = m(m(2,a),b) 1 2 开始 a b

100 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) = m(2,ab) = m(m(2,a),b) = m(1,b) 1 2 开始 a b 状态序列：

101 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) = m(2,ab) = m(m(2,a),b) = m(1,b) 1 2 开始 a b

102 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab)
= m(m(1,b),ab) = m(2,ab) = m(m(2,a),b) = m(1,b) = 2 1 2 开始 a b 状态序列： accepted

103 基于DFA构建识别程序 建立状态转移表。 每一步状态转换通过查表得到下一步状态转换目标。

104 小 结 计算机实现 正规式 状态转换图 不确定有限自动机 确定有限自动机 最简确定有限自动机 确定有限自动机 语言
等价 用正规式语法结构来指导构造过程 等价 子集构造法 合并不可区别状态 不确定有限自动机 确定有限自动机 最简确定有限自动机 状态列举法 确定有限自动机 语言