=>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc
推导二:
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaaBBCCBC =>aaaBBCBCC =>aaabBCBCC
=>aaabbCBCC
=>aaabbBCCC =>aaabbbCCC
=>aaabbbcCC
=>aaabbbccC
=>aaabbbccc
四、判断语言{0n1n0n|n>=1}是否为RL,如果是,请构造出它的有穷描述(FA,RG或者RL);如果不是,请证明你的结论(12分)
解:设L={010|n>=1}。假设L是RL,则它满足泵引理。不妨设N是泵引理所指的仅
nn
n
依赖于 L的正整数,取Z=0N1N0N 显然,Z∈L 。
按照泵引理所述,必存在u,v,w。由于|uv|<=N,并且|v|>=1,所以v只可能是由0组成的非空串。不妨设v=0,k>=1 此时有u=0
k
N k j
,w=010
jNN
从而有
uviw=0
N k j
(0)010 当i=2时,有uvw=0
k
i
jN
N
2N k
10 又因为k>=1,
N
N
所以 N+k>N 这就是说0
N k
10不属于L,
N
N
这与泵引理矛盾。所以,L不是RL。
五、构造等价于下图所示DFA的正则表达式。(12分)

0 +(1+00)((1+00*1)0)*00*)
3
年 月 日 《形式语言与自动机理论》试题一、 二、 三、 试述正规文法、有穷自动机的概念,相互之间的关系作用。 试述上下文无关文法、下推自动机的概念,相互...
形式语言与自动机试题(A卷)_理学_高等教育_教育专区。清华大学本科生考试试题... 形式语言与自动机试题 2页 免费 形式语言与自动机理论试... 3页 免费 形式...
形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和集合{ε ,0,00}的幂集 2. 设∑={0,1},请给出∑上的下列语言的文法 (1...
形式语言与自动机理论试题答案解析_计算机硬件及网络_IT/计算机_专业资料。形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和...
形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式...题参见下题: 11、给定 RG G1 = (V1 , T1 , P , S1 ) 1 G2 = ...
形式语言与自动机考题2012_计算机硬件及网络_IT/计算机_专业资料。西安交大形式... 形式语言与自动机试卷 3页 2下载券 形式语言与自动机理论试... 6页 免费 ...
电子科技大学 博士学位论文 形式语言与自动机理论若干问题研究 姓名:陈文宇 申请学位级别:博士 专业:计算机应用技术 指导教师:孙世新 20091125 摘要 摘要 计算理论是...
形式语言与自动机理论-蒋宗礼-第三章参考答案_工学_高等教育_教育专区。形式...( M 1 ) 注:转化成相应的 DFA 进行处理,然后可参考第 8 题的思路 证明:...
形式语言与自动机理论试题 3页 免费 形式语言与自动机理论-04 50页 2财富值 形式语言与自动机理论-03 33页 2财富值喜欢此文档的还喜欢 形式语言与自动机理论...
形式语言与自动机理论-蒋宗礼-第四章参考答案_工学_高等教育_教育专区。形式...题 (L1∪{ε })*=L1*其中 L1 为正则语言 又 r 为正则表达式 正则语言...
热门文档