编译原理(实验6)正规式nfa确定化和最小化等

第一题：

(1)构造一个正规式，它接受={a，b}上所有包含ab的字符串。 (2)构造一个正规式，它接受={a，b}上所有以ab结尾字符串。 (3)构造一个正规式，它接受={a，b,c}上符合以下规则的字符串：

如果以a开头，则串内至少包含一个c；如果以b开头，则串内至多包含一个 a。

答：（1）、(a|b)*(ab)+(a|b)* (2)、(a|b)*ab

(3)、(a+b*c+(a|b)*)|(b+c*a(c|b)*)

第二题：试构造正规表达式((0*|1)(1*0)) *的NFA，然后确定化和最小化。 答

：

q0={0,1,2,3,5,6,7,9,10,12};

f(q0,0)= 4、13的闭包={0,1,2,3,4,5,6,7,9,10,12,13,14}; f(q0,1)=8、11的闭包={8,6,9,10,12}；

令q1={0,1,2,3,4,5,6,7,9,10,12,13,14},q2={8,6,9,10,12}； f(q1,0)=4、13的闭包=q1; f(q1,1)=8、11的闭包=q2;

f(q2,0)=11 的闭包={13,14,0,1,2,3,5,6,7,9,10,12}; f(q2,1)=11的闭包={10,11,12}；

令q3={13,14,0,1,2,3,5,6,7,9,10,12},q4={10,11,12}; f(q3,0)=4、13的闭包=q1; f(q3,1)=8、11的闭包=q2;

f(q4,0)=13的闭包=q3; f(q4,1)=11的闭包=q4;

q0 q1 q2 q3 q4

π:{q0,q2,q4}、{q1、q3}; {q0,q2,q4}0={q1,q3};

{q0,q2,q4}1={q2,q4},属于{q0,q2,q4}； {q1,q3}0={q1},属于{q1,q3}; {q1,q3}1={q2,q4},属于{q0,q2,q4}. q0 q1

0 q1 q1 1 q0 q0 0 q1 q1 q3 q1 q3 1 q2 q2 q4 q2 q4

第三题：请说明lex是如何自动构造词法分析程序的，在其自动构造的各个阶段分别应用了课本上的哪个知识点（必须具体到书本上哪一页的哪个算法或概念）。 答： 83页3.5.2 ：

Lex 系统的翻译程序对lex 源程序进行处理，生成名为lex.yy.c 的C语言程序文件 。最后用C编译程序对lex.yy.c 进行编译，并将支持扫描器运行的有关库函数连入目标码程序，便得到了想要的此法分析程序。

首先，自动构造此法分析器得从lex 源程序的正规式出发， 逐步构造能够识别这些正则式所定义的单词列的最小确定有限自动机。 它包括正规表达式正规集等概念及有限自动机化、确定化和最小化三个算法。

72页3.4.1：正规表达式与正规集的定义；

59页3.3有限自动机、确定的有限自动机及60页非确定的有限自动机。 66页3.3.5具有ε动作的NFA的确定化——子集法。 69页DFA状态数的最小化。