编译原理期中考试试卷
一、（10分）解释下列术语及概念。

1、字母表
2、串，句子
3、字母表的闭包
4、编译程序
二、（5分）编译程序有那些主要成分构成？各自的主要功能是什么？
三、（5分）什么是解释程序？它与编译程序的主要不同是什么？
四、（10分）文法G=（{A，B，S}，{a,b,c}，P，S）其中P为：
S→Ac|aB
A→ab
B→bc
写出G[S]所表示的语言。

五、（10分）文法G[N]为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
G[N]表示的语言是什么？
六、（10分）写文法，使其语言是偶正整数的集合，要求不允许0打头。

七、（10分）DFA的M＝({S,U,V,Q},{a,b},f,S,{Q})，其中f为：
f(S,a)=U, f(S,b)=V, f(U,a)=Q
f(U,b)=V, f(V,a)=U, f(V,b)=Q
f(Q,a)=Q, f(Q,b)=Q
画出DFA的状态图。

八、（10分）将下面NFA确定化。

九、（10分）将下面的DFA最小化。

十、（10分）NFA M状态图如下，求正规式R，是L(R)=L(M).
十一、（10分）L(R) =(a|b)*(aa|bb)(a|b)*, 构造NFA N使L(N)使与L(R) 等价。