形式语言与自动机理论蒋宗礼第五章参考答案.docxVIP

形式语言与自动机理论：蒋宗礼第五章参考答案

引言

形式语言与自动机理论是计算机科学的重要基础理论之一，它研究了形式语言和自动机的基本性质和相互关系。本文将围绕蒋宗礼教授的著作《形式语言与自动机理论》第五章展开讨论，并给出相应的参考答案。

正文

5.1非确定性有限自动机

5.1节介绍了非确定性有限自动机（NondeterministicFiniteAutomaton，NFA）的概念和性质。NFA是一种计算模型，具有有限的状态集合、输入字母表、状态转移函数以及初始状态和终止状态集合。与确定性有限自动机（DFA）相比，NFA的状态转移函数可以有多个转移选项，且接受输入字符串的方式是非确定的。对于同一个输入串，NFA可以有多个可能的执行路径。

练习题1：给定以下NFA：

Q={q0,q1,q2},∑={0,1},δ,q0,F

δ(q0,0)={q0,q1}

δ(q0,1)={q0}

δ(q1,0)={q2}

δ(q2,1)={q2}

q0=q0

F={q2}

请用状态转移表表示该NFA。

解答：||0|1||—|—|—||q0|{q0,q1}|{q0}||q1|-|-||q2|-|{q2}|

练习题2：将以下正则表达式转换为NFA，并用状态转移图表示（设输入字母表为{0,1}）：(a|b)*abb

解答：（此处省略了具体的构造步骤，仅给出最终的状态转移图，中间过程可参考教材）NFA状态转移图

5.2非确定性有限自动机的确定化

5.2节介绍了如何将NFA转化为DFA，即确定化。确定化的目的是将非确定性自动机转化为等价的确定性自动机，使得每个输入字符在每个状态下的转移是唯一确定的。

练习题3：将下面的NFA确定化。

Q={q0,q1,q2},∑={a,b},δ,q0,F

δ(q0,a)={q1}

δ(q0,b)={q1}

δ(q1,a)={q0,q2}

δ(q1,b)={q2}

δ(q2,a)={q2}

δ(q2,b)={q0,q1}

q0={q0}

F={q0,q2}

解答：首先构造等价的DFA状态集合。根据NFA的初始状态q0，我们可以得到等价的DFA初始状态{q0}。然后利用子集构造法：|DStates|a|b||———-|—————-|—————-||{q0}|{q1}|{q1}||{q1}|{q0,q2}|{q2}||{q0,q2}|{q1}|{q1}||{q1,q2}|{q0,q2}|{q2}||{q0,q1}|{q1}|{q1}||{q0,q1,q2}|{q1,q2}|{q1,q2}|所以，确定化后的DFA如下所示：

Q={{q0},{q1},{q0,q2},{q1,q2},{q0,q1},{q0,q1,q2}},∑={a,b},δ,{q0},{q0,q2}

δ({q0},a)={q1}

δ({q0},b)={q1}

δ({q1},a)={q0,q2}

δ({q1},b)={q2}

δ({q0,q2},a)={q1}

δ({q0,q2},b)={q1}

δ({q1,q2},a)={q0,q2}

δ({q1,q2},b)={q2}

δ({q0,q1},a)={q1}

δ({q0,q1},b)={q1}

δ({q0,q1,q2},a)={q1,q2}

δ({q0,q1,q2},b)={q1,q2}

5.3非确定性有限自动机的最小化

5.3节介绍了如何将DFA最小化。最小化的目的是去除等价的状态，使得DFA的状态数最少。

练习题4：将以下DFA进行最小化。

Q={q0,q1,q2,q3,q4},∑={0,1},δ,q0,F

δ(q0,0)=q1

δ(q0,1)=q2

δ(q1,0)=q3

δ(q1,1)=q2

δ(q2,0)=q3

δ(q2,1)=q4

δ(q3,0)=q3

δ(q3,1)=q4

δ(q4,0)=q3

δ(q4,1)=q2

q0=q0

F={q1,q4}

解答：首先构造一个状态划分表。根据终态和非终态的划分，我们可以得到如下的初始状态划分表：||0|1||—|—|—||q0|F|||q1||F||q2|F|||q3||F