📄 3.3.1e.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.3.1d.htm'" src="../images/previous.gif"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2a.htm'" src="../images/next.gif"></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td width=10></td>
<td colspan=2>
<p>下面，形式地定义ε-closure(s)。令edge(t,a)是NFA中从状态t出发沿标记为a的弧所能到达的状态集。对于一个状态集s，ε-closure（s）是一个状态集，这个状态集是从S中任一状态在没有消耗任一输入字符的情况下到达的所有状态。即，仅沿ε弧到达的状态集合。ε-closure（S）是最小集合，满足<B>T=S∪（∪edge(t,ε)）</b>，通过如下的迭代计算T， </p>
<table>
<tr>
<td width=90></td>
<td>
T:=S; <br>
<font color=blue>REPEAT</font> <br>
T':=T; <br>
T :=T' ∪（∪edge(t,ε)）; <br>
<font color=blue>UNTIL</font> T=T';
</td>
</tr>
</table>
<p>现在，象上面一样模拟NFA动作，假设我们处在NFA的状态S<sub>i</sub>,S<sub>j</sub>,S<sub>k</sub>的一个集合d={S<sub>i</sub>,S<sub>j</sub>,S<sub>k</sub>}中，从d开始并且吃进一个输入符号a，我们到达NFA的一个新的状态集，我们称这个状态集为DFA edge(d,a)</p>
<p> <font class="definition3">DFA edge(d,a)=ε-closure（∪edge(t,a)） 其中t∈d</font></p>
<p>在有了ε-closure和DFA edge的算法后，从一个NFA构造一个DFA变得容易。我们构造一个DFA，使得NFA的每个状态集相对应于DFA的一个状态。开始是ε-closure(t<sub>1</sub>)，其中t<sub>1</sub>是NFA的开始状态，若d<sub>j</sub>=DFAedge(d<sub>i</sub>,a)，那么，从d<sub>i</sub>到d<sub>j</sub>存在一条用a标识的弧。
<br>
<br>
<img class="dingyi" src="img/suanfa.gif"><b>算法3.2</b> 从一个NFA构造一个与之等价的DFA<br>
<br>
<table>
<tr>
<td width=120></td>
<td>
states[1] :=ε-closure({t<sub>1</sub>}); <br>
p:=1;j:=1; <br>
<font color=blue>WHILE</font> j<=p DO <br>
<font color=blue>BEGIN</font> <br>
<font color=blue>for</font> each a∈Σ <br>
<font color=blue>BEGIN</font> <br>
e:=DFAedge(states[j],a); <br>
<font color=blue>IF</font> e=states[i] for some i<=p <font color=blue>THEN</font> <br>
trans[j,a]=i <br>
<font color=blue>ELSE BEGIN</font> <br>
p:=p+1;<br>
states[p]:=e;<br>
trans[j,a]:=p;<br>
<font color=blue>END</font>;<br>
<font color=blue>END</font>; <br>
j:=j+1; <br>
<font color=blue>END</font>;
</td>
</tr>
</table>
<p> <br>
对图3.6(a)显示的NFA，使用算法3.2，得到下面的转换表3.2，根据表3.2，可画出图3.6(b)。 <br>
<br>
</p>
<center>
表3.2
<table width="75%" border="1" align="center" cellspacing="0" cellpadding="5">
<tr>
<td width="51%">
<div align="center">states</div>
</td>
<td width="24%">
<div align="center">a</div>
</td>
<td width="25%">
<div align="center">b</div>
</td>
</tr>
<tr>
<td height="96" width="51%">
<div align="center">
<p>{0,1,2,4,7}</p>
<p>{1,2,3,4,6,7,8}</p>
<p>{1,2,4,5,6,7}</p>
<p>{1,2,4,5,6,7,9} </p>
<p>{1,2,4,5,6,7,10} </p>
</div>
</td>
<td height="96" width="24%">
<div align="center">
<p>2</p>
<p>2</p>
<p>2</p>
<p>2</p>
<p>2</p>
</div>
</td>
<td height="96" width="25%">
<div align="center">
<p>3</p>
<p>4</p>
<p>3</p>
<p>5</p>
<p>3</p>
</div>
</td>
</tr>
</table>
</center>
<div align=left><b>观看演示 </b><font color=blue onmouseover="javascript:style.cursor='hand';" onclick="javascript:open('program/test3_4/page1.htm','_blank','left=100,top=100,scrollbars=yes,resizable=yes,width=800,height=600')">将带有ε转移的NFA转化为与之等价的DFA</font><img src="../images/yanshi.gif" ></div>
</td>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1d.htm'" src="../images/previous.gif"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2a.htm'" src="../images/next.gif"></td>
</tr>
</table>
</BODY>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -