有限自动机与词法分析器.PPT

第三章 有限自动机与词法分析器任课教师王养廷主要内容n 正则表达式到有穷自动机的转换n 有穷自动机到正则表达式的转换n 实例1 正则表达式到有穷自动机n 正则定理对任意正则表达式 RE，均可构造出一个有穷自动机 FA，使得 FA所接受的字符串等价于 RE所定义的正则集。正则表达式 RE与有穷自动机 FA等价1 正则表达式到有穷自动机n 正则表达式到有穷自动机的转换正则表达式到 NFANFA到 DFA转换DFA极小化DFA等价性1 正则表达式到有穷自动机n 结构化自动机 RE = RE = a1 正则表达式到有穷自动机n 结构化自动机 RE = A | B RE = AB1 正则表达式到有穷自动机n 结构化自动机 RE = A*1 正则表达式到有穷自动机n 结构化自动机举例 a a | b ab a* a(b|c) (a|b)(a|c) (a|b)c*2 有穷自动机到正则表达式n 举例 a a*2 有穷自动机到正则表达式n 举例