形式语言与自动机理论(第2版),清华大学出版社 北京工业大学计算机学院蒋宗礼老师主编
1.写出表示下列语言的正则表达式。 (吴贤珺 02282047) ⑴ {0, 1}*。
解:所求正则表达式为:(0+1)*。 ⑵ {0, 1}+。
解:所求正则表达式为:(0+1)+。
+
⑶ { x│x∈{0,1}且x中不含形如00的子串 }。
解:根据第三章构造的FA,可得所求正则表达式为:1*(01+)*(01+0+1)。 ⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。
解:根据上题的结果,可得所求正则表达式为:ε+1*(01+)*(01+0+1)。
+
⑸ { x│x∈{0,1}且x中含形如10110的子串 }。 解:所求正则表达式为:(0+1)*10110(0+1)*。
+
⑹ { x│x∈{0,1}且x中不含形如10110的子串 }。 解:根据第三章的习题,接受x的FA为:
要求该FA对应的正则表达式,分别以q0、q1、q2、q3、q4为终结状态考虑: q0为终态时的正则表达式:(0*(11*0(10)*(ε+111*11*0(10)*)0)*)* q1为终态时的正则表达式:0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2为终态时的正则表达式:0*11*0((10)*(111*11*0)*(00*11*0)*)*
q3为终态时的正则表达式:0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式:0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)* 将以上5个正则表达式用“+”号相连,就得到所要求的正则表达式。
+
⑺ { x│x∈{0,1}且当把x看成二进制数时,x模5与3同余和x为0时,│x│=1
且x≠0时,x的首字符为1}。
解:先画出状态转移图,设置5个状态q0、q1、q2、q3、q4,分别表示除5的余数是0、1、2、3、4的情
形。另外,设置一个开始状态q.由于要求x模5和3同余,而3模5余3,故只有q3可以作为终态。由题设,x=0时,│x│=1,模5是1,不符合条件,所以不必增加关于它的状态。下面对每一个状态考虑输入0和1时的状态转移。
q: 输入1,模5是1,进入q1。
q0: 设x=5n。输入0,x=5n*2=10n,模5是0,故进入q0 输入1,x=5n*2+1=10n+1,模5是1,故进入q1
q1:设x=5n+1。输入0,x=(5n+1)*2=10n+2,模5是2,故进入q2 输入1,x=(5n+1)*2+1=10n+3,模5是3,故进入q3 q2:设x=5n+2。输入0,x=(5n+2)*2=10n+4,模5是4,故进入q4 输入1,x=(5n+2)*2+1=10n+5,模5是0,故进入q0 q3:设x=5n+3。输入0,x=(5n+3)*2=10n+6,模5是1,故进入q1

形式语言与自动机理论-蒋宗礼-第一章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第三章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论--第四章(蒋宗礼) 隐藏>> 形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? 课程性质–技术基础 ...
形式语言与自动机理论(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机理论(蒋宗礼)课件形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 ...
形式语言与自动机理论--第二章(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机课件--蒋宗礼形式语言与自动机理论 Formal Languages and Automata Theory 蒋...
形式语言与自动机理论--第六章(蒋宗礼)_物理_自然科学_专业资料。形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? ...
形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? 课程性质–技术基础 ? 基础知识要求–数学分析(或者高等数学),离散数学 ...
形式语言与自动机理论--第五章(蒋宗礼)_工学_高等教育_教育专区。形式语言与自动机课件--蒋宗礼形式语言与自动机理论 Formal Languages and Automata Theory 蒋...
形式语言与自动机理论--第八章(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机理论 Formal Languages and Automata Theory 蒋宗礼 课程目的和基本要求 ? ...
热门文档