編譯原理課后答案

第二章2.4為下列語言寫正規(guī)定義

C語言的注釋，即以

/*

開始和以

*/

結(jié)束的任意字符串，但它的任何前綴（本身除外）不以

*/

結(jié)尾。

［解答］

other

→

a

|

b

|

…

other指除了*以外C語言中的其它字符

other1

→

a

|

b

|

…

other1指除了*和/以外C語言中的其它字符

comment

→

/*

other*

(*

**

other1

other*)*

**

*/

(f)

由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串。［解答］

由題目分析可知，一個符號串由0和1組成，則0和1的個數(shù)只能有四種情況：

x

偶數(shù)個0和偶數(shù)個1（用狀態(tài)0表示）；

x

偶數(shù)個0和奇數(shù)個1（用狀態(tài)1表示）；

x

奇數(shù)個0和偶數(shù)個1（用狀態(tài)2表示）；

x

奇數(shù)個0和奇數(shù)個1（用狀態(tài)3表示）；

所以，

x

狀態(tài)0（偶數(shù)個0和偶數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和奇數(shù)個1（狀態(tài)1）

x

狀態(tài)0（偶數(shù)個0和偶數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和偶數(shù)個1（狀態(tài)2）

x

狀態(tài)1（偶數(shù)個0和奇數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和偶數(shù)個1（狀態(tài)0）

x

狀態(tài)1（偶數(shù)個0和奇數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和奇數(shù)個1（狀態(tài)3）

x

狀態(tài)2（奇數(shù)個0和偶數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和奇數(shù)個1（狀態(tài)3）x

狀態(tài)2（奇數(shù)個0和偶數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和偶數(shù)個1（狀態(tài)0）

x

狀態(tài)3（奇數(shù)個0和奇數(shù)個1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個0和偶數(shù)個1（狀態(tài)2）

x

狀態(tài)3（奇數(shù)個0和奇數(shù)個1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個0和奇數(shù)個1（狀態(tài)1）

因為，所求為由偶數(shù)個0和偶數(shù)個1構(gòu)成的所有0和1的串，故狀態(tài)0既為初始狀態(tài)又為終結(jié)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖：由此可以寫出其正規(guī)文法為：

S0

→

1S1

|

0S2

|

ε

S1

→

1S0

|

0S3

|

1

S2

→

1S3

|

0S0

|

0

S3

→

1S2

|

0S1在不考慮S0

→

ε產(chǎn)生式的情況下，可以將文法變形為：

S0

=

1S1

+

0S2

S1

=

1S0

+

0S3

+

1

S2

=

1S3

+

0S0

+

0

S3

=

1S2

+

0S1

所以：

S0

=

(00|11)

S0

+

(01|10)

S3

+

11

+

00

(1)

S3

=

(00|11)

S3

+

(01|10)

S0

+

01

+

10

(g)

由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1的串。［解答］

此題目我們可以借鑒上題的結(jié)論來進行處理。

對于由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1的串，我們分情況討論：

(1)

若符號串首字符為0，則剩余字符串必然是奇數(shù)個0和奇數(shù)個1，因此我們必須在上題偶數(shù)個0和偶數(shù)個1的符號串基礎(chǔ)上再讀入10（紅色軌跡）或01（藍色軌跡），又因為在0→1和1→3的過程中可以進行多次循環(huán)（紅色虛線軌跡），同理0→2和2→3（藍色虛線軌跡），所以還必須增加符號串(00|11)*，我們用S0表示偶數(shù)個0和偶數(shù)個1，用S表示偶數(shù)個0和奇數(shù)個1則其正規(guī)定義為：S

→

0(00|11)*(01|10)

S0

S0

→

((00|11)|(01|10)

(00|11)*

(01|10))*

(2)

若符號串首字符為1，則剩余字符串必然是偶數(shù)個0和偶數(shù)個1，其正規(guī)定義為：

S

→

1S0

S0

→

((00|11)|(01|10)

(00|11)*

(01|10))*

綜合(1)和(2)可得，偶數(shù)個0和奇數(shù)個1構(gòu)成的所有0和1串其正規(guī)定義為：

S

→

0(00|11)*(01|10)

S0|1S0

S0

→

((00|11)|(01|10)

(00|11)*

(01|10))*

2.7(c)((ε|a)b*)*εεε01a23ε45εεεεεε67b58εsfεεεstartababbab:s->4->0->1->5->6->7->8->4->0->1->5->6->7->6->7->8->4->0->1->5->6->7->8->f2.12

為下列正規(guī)式構(gòu)造最簡的DFA

(b)

(a|b)*

a

(a|b)

(a|b)

(1)

根據(jù)算法2.4構(gòu)造該正規(guī)式所對應(yīng)的NFA，如圖所示。

(2)

根據(jù)算法2.2（子集法）將NFA轉(zhuǎn)換成與之等價的DFA（確定化過程）

初始狀態(tài)

S0

=

ε-closure(0)

=

{0,

1,

2,

4,

7}

標記狀態(tài)S0

S1

=

ε-closure(move(S0,

a))

=

ε-closure({5,

8})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11}

S2

=

ε-closure(move(S0,

b))

=

ε-closure({3})

=

{1,

2,

3,

4,

6,

7}

標記狀態(tài)S1

S3

=

ε-closure(move(S1,

a))

=

ε-closure({5,

8,

12})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

12,

13,

14,

16}

S4

=

ε-closure(move(S1,

b))

=

ε-closure({3,

10})

=

{1,

2,

4,

5,

6,

7,

10,

13,

14,

16}

標記狀態(tài)S2

S1

=

ε-closure(move(S2,

a))

=

ε-closure({5,

8})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11}

S2

=

ε-closure(move(S2,

b))

=

ε-closure({3})

=

{1,

2,

3,

4,

6,

7}

標記狀態(tài)S3

S5

=

ε-closure(move(S3,

a))

=

ε-closure({5,

8,

12,

17})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

12,

13,

14,

16,

17,

18}

S7

=

ε-closure(move(S6,

a))

=

ε-closure({5,

8,

17})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

17,

18}

S8

=

ε-closure(move(S6,

b))

=

ε-closure({3,

15})

=

{1,

2,

3,

4,

6,

7,

15,

18}

標記狀態(tài)S7

S3

=

ε-closure(move(S7,

a))

=

ε-closure({5,

8,

12})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

12,

13,

14,

16}

S4

=

ε-closure(move(S7,

b))

=

ε-closure({3,

10})

=

{1,

2,

4,

5,

6,

7,

10,

13,

14,

16}

標記狀態(tài)S8

S1

=

ε-closure(move(S8,

a))

=

ε-closure({5,

8})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11}

S2

=

ε-closure(move(S8,

b))

=

ε-closure({3})

=

{1,

2,

3,

4,

6,

7}

由以上可知，確定化后的DFA的狀態(tài)集合S

=

{S0,

S1,

S2,

S3,

S4,

S5,

S6,

S7,

S8}，輸入符號集合Σ

=

{a,

b}，狀態(tài)轉(zhuǎn)換函數(shù)move如上，S0為開始狀態(tài)，接收狀態(tài)集合F

=

{S5,

S6,

S7,

S8}，其狀態(tài)轉(zhuǎn)換圖如下所示：(3)

根據(jù)算法2.3過將DFA最小化

第一次劃分：{S0,

S1,

S2,

S3,

S4}

{S5,

S6,

S7,

S8}

{S0,

S1,

S2,

S3,

S4}a

=

{S1,

S3,

S1,

S5,

S7}

第二次劃分：{S0,

S1,

S2}

{S3,

S4}

{S5,

S6,

S7,

S8}

{S0,

S1,

S2}a

=

{S1,

S3,

S1}

第三次劃分：{S0,

S2}

{S1}

{S3,

S4}

{S5,

S6,

S7,

S8}

{S0,

S2}a

=

{S1}

{S0,

S2}b

=

{S2}

S0,

S2不可區(qū)分，即等價。{S5,

S6,

S7,

S8}a

=

{S5,

S7,

S3,

S1}

第四次劃分：{S0,

S2}

{S1}

{S3,

S4}

{S5,

S6}

{S7,

S8}

{S3,

S4}a

=

{S5,

S7}

第五次劃分：{S0,

S2}

{S1}

{S3}

{S4}

{S5,

S6}

{S7,

S8}

{S5,

S6}a

=

{S5,

S7}

第六次劃分：{S0,

S2}

{S1}

{S3}

{S4}

{S5}

{S6}

{S7,

S8}

{S7,

S8}a

=

{S3,

S1}第七次劃分：{S0,

S2}

{S1}

{S3}

{S4}

{S5}

{S6}

{S7}

{S8}

集合不可再劃分，所以S0,

S2等價，選取S0表示{S0,

S2}，其狀態(tài)轉(zhuǎn)換圖，即題目所要求的最簡DFA如下所示：第三章3.13.23.103.113.203.23第四章4.1題目有點不同方法一樣4.7（a)4.10（a)第六章6.36.56.126.236.9c語言函數(shù)f的定義如下：intf(intx,*py,**ppz){**ppz+=1;*py+=2;x+=3;returnx+*py+**ppz;}變量a是一個指向b的指針；變量b是一個指向c的指針，而c是一個當(dāng)前值為4的整數(shù)變量。如果我們調(diào)用f（a，b，c），返回值是什么？第七章7.13C語言的for語句有下列形式：For（e1;e2;e3）st