第三章 编译原理参考答案(1).doc

一:有语言L={w|w∈{0,1}*，并且w中至少有两个1，又在任何两个1之间有偶数个0 }，试写出该语言的正规表达式。

对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*

二：设语言L是满足下述条件的符号串构成的语言： 若出现 a ，则其后至少紧跟两个 c ；请给出识别 L 的正规表达式。 其中字母表为{a,b,c}
(acc|b|c)*

三：写出下面NFA识别的正规式

(a|b)ab*

三：已知文法G1:
S→aB|ε
B→bC|bD
C→cB|c
D→d
试构造其对应的最小DFA,并给出状态转换图和构造过程。
S
S
B
S
a
C
S
b
D
S
b
c
F
S
ε
c
d

确定化：
I
Ia
Ib
Ic
Id
{S,F}
{B}

{B}

{C,D}

{C,D}

{F,B}
{F}
{F,B}

{C,D}

{F}

1
S
2
S
a
3
S
b
4
S
b
5
S
d
c

最小化：
{1，5，4} {2，3}
{1}{5}{4}{2}{3}
上图即为最小DFA

四:设有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}。
(1) 给出描述该语言的正规表达式；
(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)并化简。

该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图：

确定化：（按照定义，上图已经是DFA，所以下面确定化不做也是可以的，直接最小化）

由最小化方法得到
{0,2} {1} {3,5} {4,6} {7}
最简的DFA：

五： 将图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)并化简。其中，X为初态，Y为终态。然后根据最小DFA，写出对应的正规文法（右线性）

A->aB|bC
B->aF|a|bE|b
C->bD
D->aD|bF|b
E->aF|a|bD
F->aF|bF|a|b