注：考试期间试卷不允许拆开。
第2页共2页
山东农业大学研究生课程考试专用
200
-200
学年第
学期 硕士生（博士生）
《 形式语言与自动机理论》试题（卷）A（B）
考试方式： 考试时长： 分钟
姓名：
教师姓名
学号：
学 时 学 分专业：………来自…..成 绩试题
1、 （10 分）给出 T={a} 上能满足下列条件的语言的文法： （1）L={w | |w| mod 3 =0 } （2）L={w | |w| mod 3 >0 } （3）L={w | |w| mod 3 <> |w| mod 2 } 2、 （10 分）写出下列语言的正则表达式： 0 的个数能够被 5 整除的所有 0，1 字符串的集合。 3、 （10）考虑以下两个语言： L1 = {anb2ncm | n, m ≥ 0} L2 = {anbmc2m | n, m ≥ 0} （1） 通过分别给出上述语言的文法来证明这些语言都是上下文无关的。 （2）L1∩L2 是 CFG 吗？证明你的结论的正确性。 4、 （30 分）有限状态自动机是一种特殊的图灵机，即，任意的一个有限状态自动机， 都可以转换为一个语言等价的图灵机。 对于语言 L1={w|w{a,b}*且 w 中至少有 3 个连续的 a 出现} 请完成如下任务： （1） 给出产生该语言的正规文法； （2） 给出该语言的正规表达式； （3）构造识别该语言的有限状态自动机（DFA） ： （4）构造可以识别该语言的图灵机。
注：考试期间试卷不允许拆开。
第1页共2页
山东农业大学研究生课程考试专用
（5）思考：是否可以给出一个将有限状态自动机，转换为与其语言等价的图灵机 的方法（转换步骤） 。
5、 （30 分）设语言 L2={由 0,1 构成的，并且任何前缀中 1 的个数都不比 0 的个数多的 串}，请完成如下任务： （1） 设计以空栈接受方式的 PDA，使它接受该语言。 （2） 设计以终态接受方式的 PDA，使它接受该语言。 （3） 给出产生该语言的上下文无关文法； （4） 构造可以识别该语言的图灵机。 （5） 思考： 是否可以给出一个将以终态接受方式的 PDA，转换为与其语言等价的图 灵机的方法（转换步骤） 。 6、 （10 分）概述我们所学习的有关内容。是否对有些问题，提出自己的看法和观点？ 请简单阐述。