文档库

最新最全的文档下载
当前位置:文档库 > 第三章课外训练答案

第三章课外训练答案

课外训练答案:

1:试构造生成语言L={a n b n c i|n≥1, i ≥0}的文法

解:S-〉AB A-〉aAb|ab B->cB|ε

2:已知语言L={a n bb n| n ≥1}, 写出产生L的文法。

解:S-〉aSb|abb

3:已知文法G=({A,B,C},{a,b,c},A,P)

其中产生式P由以下组成:

A →abc A →aBbc

Bb→bB Bc →Cbcc

bC →Cb aC →aaB

aC →aa

问:此文法表式的语言是什么?

解:该题通过推导到的句子的特点进行总结,语言为:{a n b n c n|n>=1}

4 请给出描述语言={a2m+1 b m+1 | m>=0}∪{a2m b m+2| m>=0}的文法

解:s->aAb|Abb

A->aaAb|ε

5已知文法G[S]为:

S→dAB

A→aA|a

B→Bb |

G[S]产生的语言是什么?G[S]能否改写为等价的正则文法?

解:语言为:{da m b n|m>0,n>=0}

可改写为正规文法:S->dA A->aB B->aB|bD|ε D->bD|ε

6:试写一文法,使其描述的语言L(G) 是能被5整除的整数集合。

解:S->D|AD|ABD

D->0|5

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

B->0|A|0B|AB

7:已知语言L={x | x∈{a,b,c}*,且x重复排列是对称的(aabcbaa,aabbaa,等)写出该语言的文法。

解: S->aSa|bSb|cSc|a|b|c|ε