课外训练答案：

1： 试构造生成语言L={anbnci|n≥1, i ≥0}的文法

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

2： 已知语言L={anbbn| 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

问：此文法表式的语言是什么？

解:该题通过推导到的句子的特点进行总结,语言为:{anbncn|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]能否改写为等价的正则文法？ 解:语言为:{dambn|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|ε

写出该