形式语言与自动机理论试题
一、按要求完成下列填空
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'
(1) {x|x {0,1}+且x以0开头以1结尾}
(设置陷阱状态,当第一个字符为1时,进入陷阱状态)

(2) {x|x {0,1}+且x的第十个字符为1}
(设置一个陷阱状态,一旦发现x的第十个字符为0,进入陷阱状态)

年 月 日 《形式语言与自动机理论》试题一、 二、 三、 试述正规文法、有穷自动机的概念,相互之间的关系作用。 试述上下文无关文法、下推自动机的概念,相互...
形式语言与自动机试题(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 为正则表达式 正则语言...
热门文档