编译原理第3章练习.doc

第三章习题

1．给出与以下图中的DFA等价的正规文法G。

b

b

Ａ

+

Ｂ

Ｃ

Ｄ

-

a

b

a

b

a

a

-

解：G(A)：A?aD|bB

B?aC

C?bA|aD|ε

D?aB|bD|ε

2．构造与以下正规式等价的DFA

(1)(a|b)*|ab*c+

(2)b|a(aa*b)*b

〔1〕答：①与之等价的εNFA为

②消除ε边后的NFA为

③确定化过程如下：

a

b

c

+-A{1,2}

B{2,3}

C{2}

-B{2,3}

C{2}

B{2,3}

D{4}

-C{2}

C{2}

C{2}

-D{4}

D{4}

得到的DFA为：

〔2〕答：此题可以直接得到DFA如下〔如果带有ε边，取消ε边，合并等价状态后同样可以该结果〕：

3．将以下DFA最小化

解答：{0,1},{2,3,4,5}?{0,1},{2,4},{3,5}

aa

ab

±=1\*GB3①=2\*GB3②=3\*GB3③

bb

4.将下面两个NFA确定化和最小化〔如果具有ε边，先删除ε边〕.

〔1〕

答：标识隐含的开始状态和结束状态，并消除ε边后得到如下NFA：

确定化过程如下：

a

b

c

开始/结束标识

重新命名的状态

{1,3,4}

{2}

{3}

+-

1

{2}

{4}

2

{3}

{3}

-

3

{4}

-

4

得到的DFA如下：

〔2〕

答案：直接进行确定化，过程为：

a

b

开始/结束标识

重新命名的状态

{1}

{2,3}

{2}

+

1

{2}

{1}

2

{2,3}

{1}

{3}

-

3

{3}

{1}

{3}

-

4

得到的DFA的状态转换图为：

现将该DFA进行最小化：

(ⅰ)按照结束或非结束状态，初始划分成两个子集，即

{1,2},{3,4}

(ⅱ)为得到下一分划，考察子集{1,2}。因为

?(1,a)=3,?(2,a)=1

故1和2可拆分，于是便得到当前划分

{1},{2},{3,4}

(ⅲ)再考虑{3,4}，因为

?(3,a)=1,?(4,a)=1，?(3,b)=4,?(4,b)=4

所以3和4不可区分，故子集{3,4}已不能再分裂。子集分裂的过程宣告结束。

(ⅳ)现选择状态3作为{3,4}的代表，将状态4从状态转换图中删去，并将原来指向4的箭头都指向3，这样，我们就得到了最小化后的DFA如下所示：

5．对于以下DFA，根据课件中给出的控制器，按照以下表格给出符号串abcbb#的识别过程。

当前状态

当前符号

剩余符号

变换后的状态

0

a

bcbb#

2

2

b

cbb#

1

1

c

bb#

3

3

b

b#

3

3

b

#

3

3

#

4