编译原理课后答案

..>第二章表达由以下正规式描述的语言..>(a)0(0|1)*0

在字母表{0,

1}上,以0开头和结尾的长度至少是2的01串(b)((ε|0)1*)*

在字母表{0,

1}上,所有的01串,包括空串(c)(0|1)*0(0|1)(0|1)

在字母表{0,

1}上,倒数第三位是0的01串(d)0*10*10*10*

在字母表{0,

1}上,含有3个1的01串..>(e)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

在字母表{0,

1}上,含有偶数个0和偶数个1的01串为以下语言写正规定义C语言的注释，即以/*

开场和以*/

完毕的任意字符串，但它的任何前缀〔本身除外〕不以*/

结尾。［解答］other

→a

|

b

|

…other指除了*以外C语言中的其它字符other1

→a

|

b

|

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

→/*

other*

(*

**

other1

other*)*

**

*/

(f)

由偶数个0和偶数个1构成的所有0和1的串。［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：*

偶数个0和偶数个1〔用状态0表示〕；*

偶数个0和奇数个1〔用状态1表示〕；*

奇数个0和偶数个1〔用状态2表示〕；*

奇数个0和奇数个1〔用状态3表示〕；所以，*

状态0〔偶数个0和偶数个1〕读入1，则0和1的数目变为：偶数个0和奇数个1〔状态1〕*

状态0〔偶数个0和偶数个1〕读入0，则0和1的数目变为：奇数个0和偶数个1〔状态2〕*

状态1〔偶数个0和奇数个1〕读入1，则0和1的数目变为：偶数个0和偶数个1〔状态0〕*

状态1〔偶数个0和奇数个1〕读入0，则0和1的数目变为：奇数个0和奇数个1〔状态3〕*

状态2〔奇数个0和偶数个1〕读入1，则0和1的数目变为：奇数个0和奇数个1〔状态3〕*

状态2〔奇数个0和偶数个1〕读入0，则0和1的数目变为：偶数个0和偶数个1〔状态0〕*

状态3〔奇数个0和奇数个1〕读入1，则0和1的数目变为：奇数个0和偶数个1〔状态2〕*

状态3〔奇数个0和奇数个1〕读入0，则0和1的数目变为：偶数个0和奇数个1〔状态1〕因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：由此可以写出其正规文法为：S0

→1S1

|

0S2

|

εS1

→1S0

|

0S3

|

1

S2

→1S3

|

0S0

|

0

S3

→1S2

|

0S1在不考虑S0

→ε产生式的情况下，可以将文法变形为：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

(2)

解(2)式得：S3

=

(00|11)*

((01|10)

S0

+

(01|10))

代入(1)式得：S0

=

(00|11)

S0

+

(01|10)

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

S0

+

(01|10))

+

(00|11)

=>

S0

=

((00|11)

+

(01|10)

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

+

(01|10)

(00|11)*(01|10)

+

(00|11)

=>

S0

=

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

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

+

(01|10)

(00|11)*

(01|10))

=>

S0

=

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

(00|11)*

(01|10))+

因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为：S0

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

(00|11)*

(01|10))*

(g)

由偶数个0和奇数个1构成的所有0和1的串。［解答］此题目我们可以借鉴上题的结论来进展处理。对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论：(1)

假设符号串首字符为0，则剩余字符串必然是奇数个0和奇数个1，因此我们必须在上题偶数个0和偶数个1的符号串根底上再读入10〔红色轨迹〕或01〔蓝色轨迹〕，又因为在0→1和1→3的过程中可以进展屡次循环〔红色虚线轨迹〕，同理0→2和2→3〔蓝色虚线轨迹〕，所以还必须增加符号串(00|11)*，我们用S0表示偶数个0和偶数个1，用S表示偶数个0和奇数个1则其正规定义为：S

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

S0

S0

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

(00|11)*

(01|10))*

(2)

假设符号串首字符为1，则剩余字符串必然是偶数个0和偶数个1，其正规定义为：S

→1S0

S0

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

(00|11)*

(01|10))*

综合(1)和(2)可得，偶数个0和奇数个1构成的所有0和1串其正规定义为：S

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

S0|1S0

S0

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

(00|11)*

(01|10))*

(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

为以下正规式构造最简的DFA

(b)

(a|b)*

a

(a|b)

(a|b)

(1)

根据算法构造该正规式所对应的NFA，如下列图。(2)

根据算法〔子集法〕将NFA转换成与之等价的DFA〔确定化过程〕初始状态S0

=

ε-closure(0)

=

{0,

1,

2,

4,

7}

标记状态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}

标记状态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}

标记状态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}

标记状态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}

S6

=

ε-closure(move(S3,

b))

=

ε-closure({3,

10,

15})

=

{1,

2,

4,

5,

6,

7,

10,

13,

14,

15,

16,

18}

标记状态S4

S7

=

ε-closure(move(S4,

a))

=

ε-closure({5,

8,

17})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

17,

18}

S8

=

ε-closure(move(S4,

b))

=

ε-closure({3,

15})

=

{1,

2,

3,

4,

6,

7,

15,

18}

标记状态S5

S5

=

ε-closure(move(S5,

a))

=

ε-closure({5,

8,

12,

17})

=

{1,

2,

4,

5,

6,

7,

8,

9,

11,

12,

13,

14,

16,

17,

18}S6

=

ε-closure(move(S5,

b))

=

ε-closure({3,

10,

15})

=

{1,

2,

4,

5,

6,

7,

10,

13,

14,

15,

16,

18}

标记状态S6

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}

标记状态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}

标记状态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的状态集合S

=

{S0,

S1,

S2,

S3,

S4,

S5,

S6,

S7,

S8}，输入符号集合Σ=

{a,

b}，状态转换函数move如上，S0为开场状态，接收状态集合F

=

{S5,

S6,

S7,

S8}，其状态转换图如下所示：(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不可区分，即等价。 {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}，其状态转换图，即题目所要求的最简DFA如下所示：第三章第四章4.1题目有点不同方法一样〔a)〔a)第六章c语言函数f的定义如下：intf(int*,*py,**ppz){**ppz+=1;*py+=2;*+=3;return*+*py+**ppz;}变量a是一个指向b的指针；变量b是一个指向c的指针，而c是一个当前值为4的整数变量。如果我们调用f〔a，b，c〕，返回值是什么？调用的顺序不正确，应该是f(c,b,a)才符合函数的定义，否则编译是通不过的。除非调用时进展强制转换。如果强制转换以后调用，f函数内，ppz是形参，是个整数指针的指针，而ppz的实参是c，它的值就是4，指向的地址空间就是错误的。py倒是可以，实参为b，指向c，*py的值就是c的值，为4。*的实参是a，实际上是个整数指针的指针，函数内当做整数来用，但是它的值是不确定的。如果按照f(c,b,a)的顺序调用，**ppz+=1后，c=*b=**a=5；*py+=2后，c=*b=**a=7，*+=3后，*=7，而c=*b=**a=