形式语言与自动机理论试题答案解析.doc

形式语言与自动机理论试题答案解析
一、按要求完成下列填空
给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4）
(1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}}
(2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
设∑={0,1},请给出∑上的下列语言的文法 （2x5）
所有包含子串01011的串
S→X01011Y
X→ε|0X|1X
Y→ε|0Y|1Y
(2)所有既没有一对连续的0，也没有一对连续的1的串
A→ε|A’|A”
A’ →0|01|01A’
A” →1|10|10A”
构造识别下列语言的DFA 2x6
(1) {x|xÎ{0，1}+且x以0开头以1结尾}
（设置陷阱状态，当第一个字符为1时，进入陷阱状态）

(2) {x|xÎ{0，1}+且x的第十个字符为1}
（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
二、判断（正确的写T，错误的写F） 5x2
{a,b,c,d,e}上的二元关系，则 ( T )
任取(x.,y),其中x,y，使得。





，Φ ( T )
：S A|AS A a|b|c|d|e|f|g 是RG ( F )
( F )
（rs+s）r=rrs（rrs） ( F )
不成立，假设r,s分别是表示语言R，S的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)(s(rs+s)*r) L(rr*s(rr*s)*)
所以s(rs+s)*r rr*s(rr*s)*,结论不成立
三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。
bB→bb
CB→BC
bC→bc
cC→cc
推导一：
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaabCBCBC
=>aaabBCCBC
=>aaabbCCBC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccC
=>aaabbbccc
推导二：