构造正规式相应的DFA(共3页).doc

精选优质文档-倾情为你奉上构造正规式相应的DFA：1(0|1)*101按照以下三步：（1）由正规表达式构造转换系统（NFA）（2）由转换系统（NFA）构造确定的有穷自动机DFA（3）DFA的最小化答：（1）首先构造与正规式1（0|1）*101相应的NFA，然后再将NFA确定化。为正规式构造NFA的方法为“语法制导”法，即依据正规式的语法构造来构造。首先将正规式r=1（0|1）*101分解成r=r1,r2r3，其中：r1=1，r2=（0|1）*，r3=101。对于r1，有：XA1对于r2，有：A0,1对于r3，有：XBCY110因此，与正规式r=r1r2r3相对应的NFA如图所示为：A0,1X1BCY110展开为：A30X1BCY110A2A11（2）将NFA转换成DFA采用子集法，即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C，