计算理论2012期中(共3页).doc

《计算理论2012期中(共3页).doc》由会员分享，可在线阅读，更多相关《计算理论2012期中(共3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上考试中心填写 年 月 日考 试 用湖南大学期中考试试卷 M M M M M M M M M M M M M M M M M M M M M M M M M M M 装订线答题不得超过此线 M M M M M M M M M M M M M M M M M M M M M M M M M姓名： 考号： 专业：课程名称： 计算理论 试卷编号： 1 考试时间：100分钟题 号一二三四五六七八九十总分应得分10101010101010101010100实得分评分：评卷人一. 画出识别下述语言的DFA状态图。（字母表为0，1）1w|w除了11和111之外的任何字符2w|w从0开

2、始的长度为奇数，从1开始的长度为偶数二. 简单证明.用来表示的值，其中p,q是既约的正整数。证明：没有这样的正整数对(p,q)，三. 把下述正则表达式转换为非确定型自动机。四. 设计接受下列语言的上下文无关文法（字母表为0，1）|。五. 利用泵引理，证明:不是正则的。六. 考虑下面的文法：这个文法是歧义的。试证明串aab的两个：1） 最左推导；2） 语法分析树；七. 设上下文无关文法G:SaAa|bBb|AC|aBC|bCCD|D A|B|ab 将上述CFG转换为乔姆斯基文法。八. 证明正则语言在下列运算下封闭：1 并。2 补。九 图灵机M的状态图如下： 0LxL q5 R L xR xR q1 q2 q3 R 0,R 0x,R 0R 0x,R xR R qreject qaccept q4 xR R在以下输入串上，给出M所进入的格局序列：1. 0002.0000十 用高水平描述的方式设计一个识别下面语言的图灵机。A=|B是DFA，B中包含无用状态有穷自动机DFA的一个无用状态，是在任何输入上都不会进入的状态。专心-专注-专业