形式语言与自动机理论试题
一、按要求完成下列填空
1.
给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 (2x4')
(1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2)
{Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
2.
设∑={0,1},请给出∑上的下列语言的文法 (2x5')
(1)所有包含子串
01011的串
S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y
(2)所有既没有一对连续的0,也没有一对连续的1的串 A→ε|A’|A”
A’ →0|01|01A’ A” →1|10|10A”
3.
构造识别下列语言的DFA 2x6'
{0,1}+且x以0开头以1结尾}
(1) {x|x
(设置陷阱状态,当第一个字符为1时,进入陷阱状态)
00110,10S1
(2) {x|x{0,1}+且x的第十个字符为1}
(设置一个陷阱状态,一旦发现x的第十个字符为0,进入陷阱状态)
0,1S0,10,10,10,10,10,10,10,10,110,1
二、判断(正确的写T,错误的写F) 5x2'
1.设R1和R2是集合{a,b,c,d,e}上的二元关系,则
(R?R)R?RR?RR1231323 ( T )
任取(x.,y),其中x,y?{a,b,c,d,e},使得(x,y)?(R1?R2)R3。
??z((x,z)?R1?R2?(z,y)?R3) z?{a,b,c,d,e} ??z((x,z)?R1?(x,z)?R2?(z,y)?R3)
??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3
2.对于任一非空集合A,Φ?2 ( T ) 3.文法G:S A|AS A a|b|c|d|e|f|g 是RG ( F ) 型语言
2型语言
1型语言
0型语言 ( T )
A?? (rs+s)*r=rr*s(rr*s)* ( F ) 不成立,假设r,s分别是表示语言R,S的正则表达式,例如当R={0},S={1}, L(s(rs+s)*r)是以1开头的字符串,而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ? L(rr*s(rr*s)*)
所以s(rs+s)*r? rr*s(rr*s)*,结论不成立
三、设文法G的产生式集如下,试给出句子aaabbbccc的至少两个不
?同的推导(12分)。
S?aBC|aSBC aB?ab bB→bb CB→BC bC→bc cC→cc
推导一: S=>aSBC
=>aaSBCBC =>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC
=>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc
推导二:
S=>aSBC
=>aaSBCBC =>aaaBCBCBC
=>aaaBBCCBC =>aaaBBCBCC
=>aaabBCBCC
=>aaabbCBCC
=>aaabbBCCC =>aaabbbCCC =>aaabbbcCC
形式语言与自动机理论试题
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)