PPT《*》

0 0

1 1 NFA : S2 S1 S0

1 0

1 1

0 0 DFA : * 《编译原理与技术》讲义 * 对于?上正规式R,存在一个NFA M,使得L(M) = L(R) ,反之亦然.Thopmson 方法: R=? R=? R=a∈? 正规式与有限自动机 S0 S1 S0 S1 S0 a 只引入初态S0和终态S1,他们之间无状态转换 * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 | R2 (1) Si fi Sj fj R1对应的NFA,Si为初态,fi为终态 R2对应的NFA,Sj为初态,fj为终态 * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 | R2 (2) S0 Si fi Sj fj 引入新的初态S0和?(S0,?)=Si和?(S0,?)=Sj ? ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 | R2 (3) S0 f0 Si fi Sj fj ? ? 引入新的终态f0和?(fi,?)=f0和?(fj,?)=f0 ? ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 ・ R2 (1) Si fi Sj fj R1对应的NFA,Si为初态,fi为终态 R2对应的NFA,Sj为初态,fj为终态 * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 ・ R2 (2) Si fi Sj fj S0 引入新的初态S0和?(S0,?)=Si ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 ・ R2 (3) Si fi Sj fj S0 引入新的状态转换?(fi,?)=Sj ? ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1 ・ R2 (4) Si fi Sj fj S0 引入新的终态f0和状态转换?(fj,?)=f0 ? ? f0 ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1* (1) Si fi R1对应的NFA,Si为初态,fi为终态 * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1* (2) Si fi S0 引入新的初态S0和?(S0,?)=Si ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1* (3) Si fi S0 ? 引入新的终态f0和状态转换?(fi,?)=f0 f0 ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1* (4) Si fi S0 ? 引入新的状态转换?(fi,?)=Si f0 ? ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= R1* (5) Si fi S0 ? 引入新的状态转换?(S0,?)=f0 f0 ? ? ? * 《编译原理与技术》讲义 * 正规式与有限自动机 R= (R1) Si fi R1对应的NFA,它也是(R1)对应的NFA * 《编译原理与技术》讲义 * e.g.12 构造(0|1)*01的对应的FA.(1)

0 0

1 1

0 |

1 ? ? ? ?

0 1 * 《编译原理与技术》讲义 * e.g.12 构造(0|1)*01的对应的FA.(2) (0 | 1) 同0|1(0 | 1)* ? ? ? ?

0 1 ? ? ? ? * 《编译原理与技术》讲义 * e.g.12 构造(0|1)*01的对应的FA.(3) (0 | 1)*

0 ? ? ? ? ?

0 1 ? ? ?

0 ? * 《编译原理与技术》讲义 * e.g.12 构造(0|1)*01的对应的FA.(4) (0 | 1)*

0 1

0 ? ? ? ? ?

0 1 ? ? ? ?

1 ? * 《编译原理与技术》讲义 * e.g.12 构造(0|1)*01的对应的FA.(5) R1 R2 | R3

0 1 ( ) R4 * R5 R7 ・ R9 ・ R6

0 R8

1 * 《编译原理与技术》讲义 * Thompson方法所构造的NFA的状态数和?转换较多.可以采用下面方法减少之: R = R1 | R2 R1 R2 R = R1 R2 R1 R2 R = R1* ? ? R1 R R R1 * 《编译原理与技术》讲义 * e.g.13 构造(0|1)*01的对应的FA-简化版 (0|1)*

0 1 1) (0|1)*

0 1 2) (0|1)*

1 3)

0 ?

1 4)

0 ?

0 |

1 * 《编译原理与技术》讲义 * e.g.13 构造(0|1)*01的对应的FA-简化版 ?

1 4)

0 ?

0 |

1 ?

1 5)

0 ?

0 1 * 《编译原理与技术》讲义 * 对于一个FA M,皆有 ?上正规式R,使得L(M) = L(R) ,反之亦然.方法如下(1)首先添加新的开始和接收状态. FA M 正规式与有限自动机 F S0 Y X ? ? 正规式与有限自动机 方法如下(2)逐个删除FA中的状态q. * 《编译原理与技术》讲义 * q q1 qn p1 pm α1 αn β1 βm ... ... γ1 γk .. q1 qn p1 pm ... ... α1(γ1|…|γk)*β1 αn(γ1|…|γk)*βm αn(γ1|…|γk)*β1 α1(γ1|…|γk)*βm 正规式与有限自动机 方法如下(3)最终形成:R = R1 | R2 … | Rt * 《编译原理与技术》讲义 * X Y R1 R2 Rt X Y R 正规式与有限自动机 针对如下FA M,给出一个正规式R,使得L(R) = L(M). * 《编译原理与技术》讲义 * S2 S1 S0