北邮计算机专业形式语言与自动机课程答案详解
(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集,可以写出表达式和画出自动机。(略) 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。
根据正则集的性质,L也是正则集。
4.对下列文法的生成式,找出其正则式
(1) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下:
S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d
(2) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下:
S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d
答:(1) 由生成式得: S=aA+B ①
A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤
③④⑤式化简消去CD,得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入①
S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得: S=aA+B ①
A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤
由③得 B=b*a ⑥
将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦
++
将⑥⑦代入② A=ba+c(d+ba) ⑧
++
将⑥⑧代入① S=a(ba+c(d+aba))+b*a =ab+a+acd+acab+a+b*a
5.为下列正则集,构造右线性文法: (1){a,b}*
(2)以abb结尾的由a和b组成的所有字符串的集合
(王柏、杨娟编著)课后习题...形式语言与自动机课后作业答案 第二章 4.找出右线性文法,能构成长度为 1 至 ...
《形式语言与自动机》(王柏、杨娟编著)北邮出版社_课后习题答案。形式语言与自动机 习题答案北京邮电大学——形式语言与自动机课后作业答案 北京邮电大学——形式语言...
形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。隐藏>> 第三章 有限自动机与右线性文法 本章主要内容确定有限自动机 非确定有限自动机...
形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。隐藏>> 第...
形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。隐藏>> 5.3 修改型图灵机基本图灵机是计算的一种通用模型,对它进 行某些修改,会...
形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。隐藏>> §...
形式语言自动机学习课件。配合《形式语言与自动机》(王柏、杨娟编著)教材。隐藏>> 范式和Greibach范式 §4.3 Chomsky范式和 范式和 范式 Chomsky范式定义: 2型...
教材: 形式语言与自动机 王柏 杨娟 编著 北京邮电大学出版社 2003.1 2013-5-8 College of Computer Science & Technology, BUPT 5 经典参考书 ? 书名 ...
电力电子技术课后习题答案... 46页 5财富值 教育学(杨秀治)山东大学出... ...36页 免费 《形式语言与自动机》(王柏... 15页 10财富值搜你所想,读你所...
教材: 形式语言与自动机 王柏 杨娟 编著 北京邮电大学出版社 2003.1 College of Computer Science & Technology, BUPT 4 经典参考书 ? 书名 Introduction to ...
热门文档