文库摘要：

2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。
答：
 ZSME | B
 S1|2|3|4|5|6|7|8|9
 M | D | MD
 D0|S
 B2|4|6|8
 E0|B
3. 设文法G为：
N D|ND
D 0|1|2|3|4|5|6|7|8|9
请给出句子123、301和75431的最右推导和最左推导。
答：NNDN3ND3N23D23123
 NNDNDDDDD1DD12D123
 NNDN1ND1N01D01301
 NNDNDDDDD3DD30D301
 NNDN1ND1N31ND31N431ND431N5431D543175431
 NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D75431 本文来自文库分享网www.wkfxw.com
4. 证明文法 SiSeS|iS| i是二义性文法。
答：对于句型iiSeS存在两个不同的最左推导：
 SiSeSiiSes
 SiSiiSeS
 所以该文法是二义性文法。
5. 给出描述下面语言的上下文无关文法。
（1） L1={anbnci |n>=1,i>=0 }
（2） L2={aibj|j>=i>=1}
（3） L3={anbmcmdn |m,n>=0}
答：
（1） SAB
AaAb | ab
BcB | 
（2） SASb |ab
Aa | 
（3） SaSd | A | 
AbAc | 
6. 设计一个最简的DFA M,使其能够识别所有的被3整除的无符号十进制整数。
答：