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

形式语言与自动机试题

一、用递归定义给出下列语言的有限描述(每题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分)。

第1页

你可能喜欢

  • 形式语言与自动机理论
  • 形式语言与自动机答案
  • 理论复习
  • 理论考试
  • 概率论与数理统计答案
  • 北京师范大学
  • 计算理论试题

热门文档

相关文档

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

    形式语言与自动机考题2012_计算机硬件及网络_IT/计算机_专业资料。西安交大形式语言与自动机《形式语言与自动机理论》期末考题 2012 年 4 月 19 日一、基本概念:...

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

    形式语言与自动机试题(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)-答案-o...

    2008—2009 第一学期形式语言与自动机考查试卷(A) 参考答案及评分标准(院系:计算机科学技术 专业:计算机科学技术 年级:2006 考核形式:开卷) 题号 一二三四五六期末...

  • 形式语言与自动机课后习题答案部分

    形式语言与自动机课后习题答案部分_哲学_高等教育_教育专区。形式语言与自动机课后习题答案部分(姜守旭版)形式语言与自动机理论 课后作业讲解付国宏黑龙江大学计算机科学...

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

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

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