一、用递归定义给出下列语言的有限描述(每题6分,共12分)
1.字母表 {a,b,c}上,以aa结尾的所有符号串的集合。
2.字母表 {a,b,c}上,每个a至少有一个b紧跟其后的所有符号串的集合。
二、文法和语言的转换(每题4分,共12分)。
1.已知语言L {anbmamcnctes|m 0,n 0,t 0,s 2},试构造相应的文法。
2.已知语言L {anb2mci|0 n m i},试构造相应的文法。
3.已知语言L { {0,1}*,且 中0的个数为奇数,1的个数为偶数},试构造相应的文法。
三、已知上下文无关文法如下,试构造其chomsky范式(12分)。 S ABa|AbAC|BabA
A Aa|a
B bBc|bC|A
C Cb|Ba|
四、已知右线性文法G[S](每题4分,共12分)
S aA
A aA|bS|a
(1) 构造FA
(2) 确定化
(3) 写出确定化后的自动机对应的正规式。
五、试用泵引理证明语言L {ambnckdl|l m n k}不是正规语言(14分)。
六、构造如下文法相应的npda(14分)。
S aAbBB|aAB|bBcA
A aBBc
B bBA|cAb|Ac
七、分别给出有穷自动机(FA)、下推自动机(PDA)和图灵机(TM)的物理模型,并指出它们的异同。如有可能,给出它们相应的应用实例(12分)。
八、设计一个图灵机用于拷贝由b构成的符号串。确切地说,也就是构造一个机器能够执行计算q0 ├qf ,其中 {b} ,q0为初态,qf为终态(12分)。
形式语言与自动机考题2012_计算机硬件及网络_IT/计算机_专业资料。西安交大形式语言与自动机《形式语言与自动机理论》期末考题 2012 年 4 月 19 日一、基本概念:...
形式语言与自动机试题(A卷)_理学_高等教育_教育专区。清华大学本科生考试试题专用纸考试课程 学号: 《形式语言与自动机》 A 卷 姓名: 2003 年 7 月 2 日 1...
形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 (2x4 ' ) (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (...
形式语言与自动机 试题_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 形式语言与自动机 试题_理学_高等教育_教育专区。 ...
形式语言与自动机理论试题_理学_高等教育_教育专区。形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 (2x4 '...
形式语言与自动机导论经典复习题_工学_高等教育_教育专区。收录了十道经典复习题,有用哦~~今日推荐 180份文档 CET四六级高分通关宝典 ...
形式语言与自动机课后习题答案_哲学_高等教育_教育专区。形式语言与自动机课后作业答案 第二章 4.找出右线性文法,能构成长度为 1 至 5 个字符且以字母为首的字...
2008—2009 第一学期形式语言与自动机考查试卷(A) 参考答案及评分标准(院系:计算机科学技术 专业:计算机科学技术 年级:2006 考核形式:开卷) 题号 一二三四五六期末...
形式语言与自动机课后习题答案部分_哲学_高等教育_教育专区。形式语言与自动机课后习题答案部分(姜守旭版)形式语言与自动机理论 课后作业讲解付国宏黑龙江大学计算机科学...
形式语言与自动机理论试题答案解析_计算机硬件及网络_IT/计算机_专业资料。形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ ,{Φ }}和集...
热门文档