下载提示
- 1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
- 2.下载该文档所得收入归上传者、原创者。
- 3.下载的文档，不会出现我们的网址水印。
文档列表
文档介绍
第三章有限自动机与词法分析器
任课教师
王养廷
主要内容
正则表达式到有穷自动机的转换
有穷自动机到正则表达式的转换
实例
1 正则表达式到有穷自动机
正则定理
对任意正则表达式RE,均可构造出一个有穷自动机FA,使得FA所接受的字符串等价于RE所定义的正则集。
正则表达式RE与有穷自动机FA等价
1 正则表达式到有穷自动机
正则表达式到有穷自动机的转换
正则表达式到NFA
NFA到DFA转换
DFA极小化
DFA等价性
1 正则表达式到有穷自动机
结构化自动机
RE = ε
RE = a
1 正则表达式到有穷自动机
结构化自动机
RE = A | B
RE = AB
1 正则表达式到有穷自动机
结构化自动机
RE = A*
1 正则表达式到有穷自动机
结构化自动机举例
a
a | b
ab
a*
a(b|c)
(a|b)(a|c)
(a|b)c*
2 有穷自动机到正则表达式
举例
Φ
ε
a
a*
2 有穷自动机到正则表达式
举例
任课教师
王养廷
主要内容
正则表达式到有穷自动机的转换
有穷自动机到正则表达式的转换
实例
1 正则表达式到有穷自动机
正则定理
对任意正则表达式RE,均可构造出一个有穷自动机FA,使得FA所接受的字符串等价于RE所定义的正则集。
正则表达式RE与有穷自动机FA等价
1 正则表达式到有穷自动机
正则表达式到有穷自动机的转换
正则表达式到NFA
NFA到DFA转换
DFA极小化
DFA等价性
1 正则表达式到有穷自动机
结构化自动机
RE = ε
RE = a
1 正则表达式到有穷自动机
结构化自动机
RE = A | B
RE = AB
1 正则表达式到有穷自动机
结构化自动机
RE = A*
1 正则表达式到有穷自动机
结构化自动机举例
a
a | b
ab
a*
a(b|c)
(a|b)(a|c)
(a|b)c*
2 有穷自动机到正则表达式
举例
Φ
ε
a
a*
2 有穷自动机到正则表达式
举例
10-第三章有限自动机与词法器试卷 来自淘豆网www.taodocs.com转载请标明出处.