1. ∑＝{a, b, c}, 构造NFA ，可以识别a,b,c 组成的串,
串中所含 a 的个数不超过1. (即可以含一个a 或不含a)
2. ∑＝{a, b, c}, 构造NFA ，可以识别a,b,c 组成的串,
串中只含一个a
3. ∑＝{a, b, c}, 构造NFA ，可以识别a,b,c 组成的串,
串中 至少含一个a
4. 构造识别标识符的自动机 l (l |d)*
5. ∑＝{a, b} , 构造NFA, 可以识别不以a 开头, 但以aa 结尾的字符串
并写出等价的正规式
b(a|b)*aa
6. ∑＝{a, b},
构造NFA, 可以识别a,b 组成的串, 每个a 后面至少紧随两个b, 并写出等价的正规式
(b|abb)*
b, c
l, d
1. 给语言 L={a
n
|n≥0} , 写3型文法，并构造自动机
可以构造出L 的自动机如下: 再将自动机转换成3型文法,
G: S →aS |ε
2. 给语言L={ a
n b m
|n,m≥1}，写3型文法，并构造自动机
可以构造出L 的自动机如下: 再将自动机转换成3型文法,
G: S →aA
A →aA|b
B B →bB|ε
3. 构造自动机 L={ a
2n+1b 2m a 2p+1
| n≥0,m≥1, p≥0 }
4. 给语言 L(G)={ a
n b m c k
|n,m,k≥0} ，写3型文法，并构造自动机
a*b*c*
G: S →aS|B
B →bB|
C C →cC|ε 将DF A 1和DF A 2确定化最小化, 得到结果相同：
a,b,c
b
5. 构造自动机，识别能被3整除的二进制数
状态0: 被3整除
状态1: 被3除余1
状态2: 被3除余2
6. 构造自动机，识别含奇数个0 且 奇数个1 的二进制数串
S: 偶数个0, 偶数个1
A: 奇数个0, 偶数个1 B: 奇数个0, 奇数个1 C: 偶数个0, 奇数个1
7. 构造文法, 产生含有偶数个1的二进制数串， ∑＝{0,1} 解法一：
G : S → 0S | 1A | ε A → 0A | 1S
解法二：
S: 偶数个0, 偶数个1 A: 奇数个0, 偶数个1 B: 奇数个0, 奇数个1 C: 偶数个0, 奇数个1
确定化，最小化，则得到解法一中的DFA
单元测试2
8. 构造自动机，识别满足以下条件的符号串：
至少含有两个1, 又在任何两个1之间有偶数个0
9. 写出下图所示自动机所描述的语言
100*|100*11*0|111*0
化简得: 10*1*0
L={10m1n0 | m≥0, n≥0}
10. 证明题：正规集的子集不一定是正规集
证明如下:
a*b* 是正规集, L1={ a n b n |n≥0}是它的子集, 但是L1不是正规集, 因为找不到一个3型文法描述L1, 即只能用2型文法描述L1
G: S→aSb|ε
