欢迎来到天天文库
浏览记录
ID：37218455
大小：262.50 KB
页数：7页
时间：2019-05-19
《形式语言试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、哈工大2004年秋季学期学号姓名形式语言试题题号一二三四五六七总分分数（总分90分）一、基本概念（每小题4分，共16分）1．简述有限状态自动机接受的语言与正则表达式之间的关系2．一个下推自动机P以终结状态方式接受的语言L(P)的定义3．DPDA的形式定义第1页（共7页）4．M为图灵机TM，描述M所接受的语言二、构造DFA（画出状态转移图），使之接受下列语言（20分）1．含有连续的三个0的0，1串2．以连续的三个0结尾的0，1串第2页（共7页）3．以连续的三个0结尾，或以001结尾的0，1串4．分别给出以上三种
2、语言的正则表达式三、描述下列自动机所接受的语言（10分）1．第3页（共7页）2．四、设或（14分）1.写出CFGG，使L(G)=L2.判断上述CFG是不是二义的，并给出理由第4页（共7页）1.将上述CFG转化为CNF形式五、试用相应的泵引理证明（15分）1．为完全平方数}不是正则语言第5页（共7页）2．不是上下文无关的六、写出与下列PDA等价的CFG，要求非终结符采用[pxq]形式（10分）第6页（共7页）七、证明一个正则语言与一个CFL的交是CFL（5分）第7页（共7页）
此文档下载收益归作者所有
