文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 形式语言与自动机理论试题
侵权投诉

形式语言与自动机理论试题

=>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

上一页第3页

你可能喜欢

热门文档

相关文档

  • 形式语言与自动机试卷

    年 月 日 《形式语言与自动机理论》试题一、 二、 三、 试述正规文法、有穷自动机的概念,相互之间的关系作用。 试述上下文无关文法、下推自动机的概念,相互...

  • 形式语言与自动机试题(A卷)

    形式语言与自动机试题(A卷)_理学_高等教育_教育专区。清华大学本科生考试试题... 形式语言与自动机试题 2页 免费 形式语言与自动机理论试... 3页 免费 形式...

  • 形式语言与自动机理论试题

    形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和集合{ε ,0,00}的幂集 2. 设∑={0,1},请给出∑上的下列语言的文法 (1...

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

    形式语言与自动机理论试题答案解析_计算机硬件及网络_IT/计算机_专业资料。形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和...

  • 形式语言与自动机理论-蒋宗礼-第二章参考答案

    形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式...题参见下题: 11、给定 RG G1 = (V1 , T1 , P , S1 ) 1 G2 = ...

  • 形式语言与自动机考题2012

    形式语言与自动机考题2012_计算机硬件及网络_IT/计算机_专业资料。西安交大形式... 形式语言与自动机试卷 3页 2下载券 形式语言与自动机理论试... 6页 免费 ...

  • 形式语言与自动机理论若干问题研究

    电子科技大学 博士学位论文 形式语言与自动机理论若干问题研究 姓名:陈文宇 申请学位级别:博士 专业:计算机应用技术 指导教师:孙世新 20091125 摘要 摘要 计算理论是...

  • 形式语言与自动机理论-蒋宗礼-第三章参考答案

    形式语言与自动机理论-蒋宗礼-第三章参考答案_工学_高等教育_教育专区。形式...( M 1 ) 注:转化成相应的 DFA 进行处理,然后可参考第 8 题的思路 证明:...

  • 形式语言与自动机理论-08

    形式语言与自动机理论试题 3页 免费 形式语言与自动机理论-04 50页 2财富值 形式语言与自动机理论-03 33页 2财富值喜欢此文档的还喜欢 形式语言与自动机理论...

  • 形式语言与自动机理论-蒋宗礼-第四章参考答案

    形式语言与自动机理论-蒋宗礼-第四章参考答案_工学_高等教育_教育专区。形式...题 (L1∪{ε })*=L1*其中 L1 为正则语言 又 r 为正则表达式 正则语言...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email