形式语言与自动机理论(第2版),清华大学出版社 北京工业大学计算机学院蒋宗礼老师主编
第三章作业答案
1.已知DFA M1与M2如图3-18所示。 (敖雪峰 02282068)
(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。

qS
q0
1

图3-18 两个不同的DFA
解答:(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3; M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;
(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:
M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]*
M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*}
******************************************************************************* 2.构造下列语言的DFA

( 陶文婧 02282085 ) (1){0,1}*
,1
(2){0,

1}
+
,1
(3){x|x {0,1}+且x中不含00的串}
(设置一个陷阱状态,一旦发现有00的子串,就进入陷阱状态)
形式语言与自动机理论-蒋宗礼-第四章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第二章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论-蒋宗礼-第一章参考答案_工学_高等教育_教育专区。形式语言与自动机理论(第2版),清华大学出版社北京工业大学计算机学院蒋宗礼老师主编...
形式语言与自动机理论--第三章(蒋宗礼) 形式语言与自动机课件--蒋宗礼形式语言与自动机课件--蒋宗礼隐藏>> 形式语言与自动机理论 Formal Languages and Automata...
形式语言与自动机理论--第八章(蒋宗礼)_理学_高等教育_教育专区。形式语言与自动机理论 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 蒋宗礼 2014-3-18 1 课程目的和基本要求 ? 课程性质–技术基础 ? 基础知识要求–数学分析(或者高等...
热门文档