📄 3.3.1a.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<BODY bgColor=Lavender>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.3b.htm'" src="../images/previous.gif"></IMG></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1b.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td colspan=3>
<font class="title2"><b>3.3 有限自动机</b></font>
</td>
</tr>
<tr>
<td height="190%" colspan="3"><br>
<p><font class="definition3">有限自动机</font>是具有离散输入与输出的系统的一种数学模型。系统可处于有限个内部“状态”的任何一个之中，系统的当前状态概括了有关过去输入的信息，这些信息对于在后来的输入上确定系统的行为是必须的。电梯的控制机构是有限状态系统的一个好例子，这个机构并不记住所有先前的服务要求，而仅仅记住现在是在几楼，运动的方向（上或下）及尚未满足的服务要求。在计算机科学中，可以找到许多有限状态系统的例子。有限自动机理论是设计这些系统的有效工具。如开关线路，文本编辑程序和词法分析程序。研究有限状态系统的重要原因是概念的自然性和应用的广泛性。有限状态系统最初的形式研究是在1913年由McCulloch和Pitts提出的。</p>
<p>有限自动机分<font class="definition3">确定的有限自动机</font>和<font class="definition3">非确定的有限自动机</font>，前者在3.2中已有详细讨论，后者除在理论上其重要作用外，在词法分析器自动生成中也起到了重要作用。下面先介绍非确定的有限自动机的概念，然后介绍它与确定的有限自动机的关系。</p>
<hr size=2 width=100% align=center color=red>
</td>
</tr>
<tr>
<td width=5></td>
<td colspan=2>
<br>
<b>3.3.1 非确定有限自动机(NFA)</b><br><br>
</td>
</tr>
<tr>
<td width=10></td>
<td colspan=2>
<p>
<img class="dingyi" src="img/dingyi.gif">
<font size=5><b>定义3．2</b></font><font class="definition2">非确定有限自动机</font>Ｍ是一个五元组</p>
<p>     Ｍ＝（Σ，Ｑ，ｑ<sub>0</sub>，Ｆ，δ）</p>
<p>其中Σ，Ｑ，ｑ<sub>0</sub>，Ｆ的意义和ＤＦＡ的定义一样，而δ是一个从ＱＸΣ∪{ε}到Ｑ的子集的映射，即 </p>
<p> δ：ＱXＳ -> ２<sup>Ｑ</sup></P>
<p> 其中2<sup>Ｑ</sup>是Ｑ的幂集，即Ｑ中所有子集组成的集合。</p>
<p>一个含有n个状态，m个输入符号的NFA M，也可以形象地通过一张状态转换图来表示，这张图含有一个状态结，每个状态结可射出若干箭弧与别的状态结相连接。准确地说，如果δ（ｑ，ａ）＝｛ｑ<sub>１</sub>，ｑ<sub>２</sub>，．．．ｑ<sub>K</sub>｝，则从ｑ出发分别向ｑ<sub>１</sub>，ｑ<sub>２</sub>，…，ｑ<sub>ｋ</sub>，各射出一条标记为ａ的箭弧（ｑ<sub>１</sub>，ｑ<sub>２</sub>，…，ｑ<sub>K</sub>∈Ｑ，ａ∈Σ∪{ε}，k可以是0），整个图含有一个初态结和若干终态结（可以是零个）。</p>
<p>对任何ｗ∈Σ<sup>*</sup>，若存在一条从初态结到终态结的道路，且这条路上所有箭弧的标记符号依次连接成的符号串恰好等于ｗ，则称ｗ可为NFA
M所识别（或接受或读出）。若ｑ<sub>０</sub>∈Σ，这时ｑ<sub>０</sub>的状态结既是初态结也是终态结，因而存在一条从初态结到终态结的ε－道路，此时空符号串ε可为NFA所接受。Σ<sup>*</sup>中所有可被NFA
M所接受的符号串的集合记为Ｌ（Ｍ）。 <br>
如果我们将非确定有限自动机中δ的定义像3.2.1结尾时一样依合理的方式延拓到ＱＸΣ<sup>*</sup>上，就可离开状态转换图形式地去定义NFA
M所识别的语言Ｌ（Ｍ）。 <br>
虽然DFA是NFA的特例，而NFA是DFA概念的推广，然而最终我们将发现被一个NFA所识别的语言，都能被一个DFA所识别。</p>
</td>
</tr>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.3b.htm'" src="../images/previous.gif"></IMG></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1b.htm'" src="../images/next.gif"></IMG></td>
</tr>
</table>
</BODY>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -