有限自动机理论04章正则语言(简化)-

第1页 / 共12页

第2页 / 共12页

第3页 / 共12页

第4页 / 共12页

第5页 / 共12页

第6页 / 共12页

第7页 / 共12页

第8页 / 共12页

第9页 / 共12页

第10页 / 共12页

定理,-NFA的开始状态可以仅有一个 -NFA的接收状态可以仅有一个,思路,s1,f1,sm,fn,改造为,s1,sm,F,S,f1,fn,推广,FA(DFA、NFA）可以仅有一个开始状态和一个接收状态。,定理,FSL对于联合、连接和迭代三种运算是有效封闭的。,分别接收语言L1和L2的FA,M1,q1,f1,M2,q2,f2,联合：构造FA,q0,f0,M1,q1,f1,M2,q2,f2,连接：构造FA,f2,M1,q1,f1,M2,q2,迭代: 构造FA,f0,M1,q1,f1,q0,正则语言的等价模型,正则语言有5种等价模型：正则文法(右线性文法)RG 正则表达式RE DFA NFA -NFA,正则语言的5种等价模型的转换,5种等价模型之间的（直接）转换,DFA 转换为RG RG转换为NFA NFA转换为RE RE转换为-NFA -NFA转换为NFA NFA转换为DFA,