编译原理课后答案

编译原理课后答案第二章2.3叙述由下列正规式描述的语言(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串2.4为下列语言写正规定义

C语言的注释，即以

/*

开始和以

*/

结束的任意字符串，但它的任何前缀（本身除外）不以

*/

结尾。

［解答］

other

→

a

|

b

|

…

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

other1

→

a

|

b

|

…

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

comment

→

/*

other*

(*

**

other1

other*)*

**

*/

(f)

由偶数个0和偶数个1构成的所有0和1的串。［解答］

由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：

x

偶数个0和偶数个1（用状态0表示）；

x

偶数个0和奇数个1（用状态1表示）；

x

奇数个0和偶数个1（用状态2表示）；

x

奇数个0和奇数个1（用状态3表示）；

所以，

x

状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1）

x

状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2）

x

状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0）

x

状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3）

x

状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3）x

状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0）

x

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

x

状态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))*

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

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

(b)

(a|b)*

a

(a|b)

(a|b)

(1)

根据算法2.4构造该正规式所对应的NFA，如图所示。

(2)

根据算法2.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)

根据算法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不可区分，即等价。{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如下所示：第三章3.13.23.103.113.203.23第四章4.1题目有点不同方法一样4.7（a)4.10（a)第六章6.36.56.126.236.9c语言函数f的定义如下：intf(intx,*py,**ppz){**ppz+=1;*py+=2;x+=3;returnx+*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。x的实参是a，实际上是个整数指针的指针，函数内当做整数来用，但是它的值是不确定的。如果按照f(c,b,a)的顺序调用，**ppz+=1后，c=*b=**a=5；*py+=2后，c=*b=**a=7，x+=3后，x=7，而c=*b=**a=7，（这是因为x为值传