最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

编译原理第二章习题答案

IT圈 admin 35浏览 0评论

2024年3月14日发(作者:寿雅爱)

2

章习题解答

1.

文法

G[S]

为:

S->Ac|aB

A->ab

B->bc

写出

L(G[S])

的全部元素

[

答案

]

S=>Ac=>abc

S=>aB=>abc

所以

L(G[S])={abc}

2.

文法

G[N]

为:

N->D|ND

D->0|1|2|3|4|5|6|7|8|9

G[N]

的语言是什么?

[

答案

]

G[N]

的语言是

V

V={0,1,2,3,4,5,6,7,8,9}

N=>ND=> =>D=>D……D

3.

已知文法

G[S]

:

Sf dAB Af aA|a B|bB

问:相应的正规式是什么?

G[S]

能否改写成为等价的正规文法?

[

答案

]

正规式是

daa*b*

相应的正规文法为

(

由自动机化简来

)

:

G[S]:S

dA A

a|aB B

aB|a|b|bC C

bC|b

也可为

(

观察得来

):G[S]:S

dA A

a|aA|aB B

bB|

&

4.

已知文法

G[Z]

:

Z->aZb|ab

写出

L(G[Z])

的全部元素。

[

答案

]

Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb

L(G[Z])={a b|n>=1}

nn

5.

给出语言

{abc

1

n>=1,m>=0}

的上下文无关文法。

nn

分析

本题难度不大,主要是考上下文无关文法的基本概念。 上下文无关文法的基 本

定义是:

A-> B ,A € Vn ,B€( VnU Vt)

*

,

注意关键问题是保证

a

n

b

n

的成立, 即“

a

b

的个数要相等”,为此,可以用一条形如

A->aAb|ab

的产生式即可解 决。

答案

构造上下文无关文法如下:

S->AB|A

A->aAb|ab

B->Bc|c

扩展

2024年3月14日发(作者:寿雅爱)

2

章习题解答

1.

文法

G[S]

为:

S->Ac|aB

A->ab

B->bc

写出

L(G[S])

的全部元素

[

答案

]

S=>Ac=>abc

S=>aB=>abc

所以

L(G[S])={abc}

2.

文法

G[N]

为:

N->D|ND

D->0|1|2|3|4|5|6|7|8|9

G[N]

的语言是什么?

[

答案

]

G[N]

的语言是

V

V={0,1,2,3,4,5,6,7,8,9}

N=>ND=> =>D=>D……D

3.

已知文法

G[S]

:

Sf dAB Af aA|a B|bB

问:相应的正规式是什么?

G[S]

能否改写成为等价的正规文法?

[

答案

]

正规式是

daa*b*

相应的正规文法为

(

由自动机化简来

)

:

G[S]:S

dA A

a|aB B

aB|a|b|bC C

bC|b

也可为

(

观察得来

):G[S]:S

dA A

a|aA|aB B

bB|

&

4.

已知文法

G[Z]

:

Z->aZb|ab

写出

L(G[Z])

的全部元素。

[

答案

]

Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb

L(G[Z])={a b|n>=1}

nn

5.

给出语言

{abc

1

n>=1,m>=0}

的上下文无关文法。

nn

分析

本题难度不大,主要是考上下文无关文法的基本概念。 上下文无关文法的基 本

定义是:

A-> B ,A € Vn ,B€( VnU Vt)

*

,

注意关键问题是保证

a

n

b

n

的成立, 即“

a

b

的个数要相等”,为此,可以用一条形如

A->aAb|ab

的产生式即可解 决。

答案

构造上下文无关文法如下:

S->AB|A

A->aAb|ab

B->Bc|c

扩展

发布评论

评论列表 (0)

  1. 暂无评论