《编译原理》3,4两章练习题
1,下图是一个(–NFA的状态转移图，应用简化的子集构造法将该 (–NFA转化为与其相等价的DFA。

2,下图表示一个 DFA，构造出与该DFA等价的最小化的DFA（即拥有的状态数目最少）。

3,求出与正规表达式 a*b+(b+c)* 等价的一个(–NFA。(直接写出结果即可)
4,设计一个 DFA，其语言为所有长度至少为2且头两个字符不相同的0，1串构成的集合（以状态转移图的形式给出）。
5,设计一个NFA，其语言为所有长度至少为2且末尾两个字符不相同的0，1串构成的集合。（以状态转移图的形式给出）。
6,设计一个正规表达式，其语言为所有至少包含2个“0”的0，1串构成的集合。7,设计如下语言的一个上下文无关文法：
L = { anbn | n≥0 }
8,(R+S)* = R*S* + S*R* 是否可以作为关于正规表达式的一条定律？为什么？
9,设计如下语言的一个上下文无关文法：
L = { anbkcm | n,k,m≥0，且n≥m }
10,G[M],M(0A | 1B
A(1C | 0M | 0
B(0C | 1M | 1
C(1A | 0B
定义的语言是什么？
11给出定义语言L＝{W | W是不含两个相邻的1的0，1 串 }的三型文法。
12．按指定类型给出下列语言的文法.
a)不以零开头的奇数集的三型文法
b) 类PASCAL风格的变量声明语句序列的上下文无关文法。一个声明语句可以声明一序列变量（变量间逗号隔开），而后是一个冒号，再后是类型，类型可以是整型，实型，字符型等等。如:
a,b,c,integer;
d,real;
13,文法G：VN = {E},VT = {& @ a} 开始符号为 E，P为
E –> &E | E@E | a
a) 说明此文法是二义的
b) 利用算符的优先性和结合性，将其改写为等价的无二义文法,其中 @ 是右结合的且优先性比& 低.
c)使用改写后的文法画出&a@a的语法树