形式语言与自动机理论试题
一、按要求完成下列填空
1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串
(2)所有既没有一对连续的0，也没有一对连续的1的串 1. 构造识别下列语言的DFA (2x6) (1) {x|x?{0，1}+且x以0开头以1结尾}
(2) {x|x?{0，1}
+
且x的第十个字符为1}
二、判断（正确的写T，错误的写F） 5x2'
1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则
(R1?R2)R3?R1R3?R2R3
A 2.对于任一非空集合A，Φ?2
3.文法G：S A|AS A a|b|c|d|e|f|g 是RG 4.3型语言
2型语言
1型语言
0型语言
?? 5.s（rs+s）*r=rr*s（rr*s）*
三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。
S?aBC|aSBC aB?ab
bB→bb
?
CB→BC bC→bc cC→cc
四、判断语言{0n1n0n|n>=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）
五、构造等价于下图所示DFA的正则表达式。(12分)
q0 S 1 0 q1 1 0 1 1 0
q3 q2 0 六、设M=（{q0,q1,q2}，{0,1}，{0,1，B}，{δ}，q0,B,{q2}）,其中δ的定义如下：
δ（q0，0）=（q0，0，R） δ（q0，1）=（q1，1，R） δ（q1，0）=（q1，0，R） δ（q1，B）=（q2，B，R）
请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）
七、根据给定的NFA，构造与之等价的DFA。（14分）
NFA M的状态转移函数如下表 状态说明 状态 0 开始状态 输入字符 1 {q0,q2} 2 {q0,q2} {q2} {q2,q1} { q0} q0 q1 q2 q3 {q0,q1} {q3,q0} ? ? {q3,q1} {q3 } 终止状态 {q3,q2}