📄 back3.3.2b.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.2a.htm'" src="../images/previous.gif" width="65" height="27"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.1a.htm'" src="../images/next.gif" width="63" height="27"></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td width=10></td>
<td colspan=2>
<p>1.<font class="definition2">根据一致性条件</font>，因为终结状态有一条到达自身的ε-道路，而非终结状态没有到达终结状态的ε-道路，故它们是可区别的。在图3.8（b）中，我们把X放在下列表项中，（ｑ<span class="down">1</span>,ｑ<span class="down">3</span>），（ｑ<span class="down">2</span>,ｑ<span class="down">3</span>），（ｑ<span class="down">3</span>,ｑ<span class="down">5</span>），（ｑ<span class="down">3</span>,ｑ<span class="down">6</span>），（ｑ<span class="down">3</span>,ｑ<span class="down">7</span>），（ｑ<span class="down">3</span>,ｑ<span class="down">8</span>）。</p>
<p>2.<font class="definition2">根据蔓延性条件</font>，对每一个状态对（ｐ，ｑ），假定还不知道它们是否可区别，则对每一个输入符号ａ∈Σ考虑</p>
<p>ｒ＝δ（ｐ，ａ），ｓ＝δ（ｑ，ａ）</p>
<p> 若对每一个ａ∈Σ，所对应的状态ｒ与ｓ均等价，则易知ｐ与ｑ等价。若存在某个ａ∈Σ使ｒ和ｓ可区别，则ｐ和ｑ可区别。这是因为，若ｒ与ｓ通过某ｗ∈Σ<span class="up">*</span>已知道ｒ与ｓ是可区别的，则通过ａｗ可知ｐ和ｑ可区别。所以若表项（ｒ，ｓ）中有Ｘ，则Ｘ也可以放到表项（ｐ，ｑ）中。若表项（ｒ，ｓ）中还没有Ｘ，则将状态对（ｐ，ｑ）置入与（ｒ，ｓ）表项相关联的表中。等将来某个时刻，如果表项（ｒ，ｓ）获得一个Ｘ，那么与（ｒ，ｓ）表项相关联的表中的每个状态对也都将得到一个Ｘ。如图3．10所示的DFAM中有一个输入符号1，使</p>
<p> （δ（ｑ<span class="down">２</span>，１），δ（ｑ<span class="down">１</span>，１））＝（ｑ<span class="down">３</span>，ｑ<span class="down">６</span>）
<br>
因表项（ｑ<span class="down">3</span>，ｑ<span class="down">6</span>）已有Ｘ，故在表项（ｑ<span class="down">1</span>，ｑ<span class="down">2</span>）中也放上一个Ｘ。
<br>
<br>
考虑表项（ｑ<span class="down">１</span>，ｑ<span class="down">５</span>），因为有一个输入符号O使
<br>
（δ（ｑ<span class="down">1</span>，0），δ（ｑ<span class="down">5</span>，0））＝（ｑ<span class="down">２</span>，ｑ<span class="down">８</span>）</p>
<p>这导致（ｑ<span class="down">1</span>，ｑ<span class="down">5</span>）被置入与（ｑ<span class="down">2</span>，ｑ<span class="down">8</span>）表项相关联的表中，但因为ｑ<span class="down">2</span>与ｑ<span class="down">8</span>等价，故不能推出ｑ1与ｑ5之间有什么肯定的结论。这时还必须考虑另外一个输入符号1，由于还有
<br>
（δ（ｑ<span class="down">１</span>，1），δ（ｑ<span class="down">５</span>，1））＝（ｑ<span class="down">６</span>，ｑ<span class="down">６</span>）
<br>
因此就可推出ｑ1与ｑ5等价。</p>
<p> 考虑（ｑ<span class="down">1</span>，ｑ<span class="down">7</span>），由于对输入符号0有
<br>
（δ（ｑ<span class="down">１</span>，0），δ（ｑ<span class="down">7</span>，0））＝（ｑ<span class="down">2</span>，ｑ<span class="down">7</span>）</p>
<p align="center"><IMG src="IMG/3.8.gif" width="687" height="268"></p>
<p>由于表项（ｑ<span class="down">３</span>，ｑ<span class="down">５</span>）已有X，故表项（ｑ<span class="down">２</span>，ｑ<span class="down">７</span>）也有Ｘ，进而表项（ｑ<span class="down">1</span>，ｑ<span class="down">0</span>）也有X。当表3．2完成之时，我们得到的结论是等价状态为：ｑ<span class="down">１</span>与ｑ<span class="down">５</span>，ｑ<span class="down">２</span>与ｑ<span class="down">８</span>，ｑ<span class="down">４</span>与ｑ<span class="down">６</span>。最少状态的DFA
M’由图3.9给出。对于上述给不等价状态做表记的形式算法，读者可编一个简单程序去实现它。</p>
<p align="center"> 表3．2等价状态的计算
<br>
</p>
<table width="75%" border="0" align="center" cellspacing="0" cellpadding="3">
<tr>
<td width="14%" style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">2</span></div>
</td>
<td width="14%" style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td width="14%">
<div align="center"></div>
</td>
<td width="14%">
<div align="center"></div>
</td>
<td width="14%">
<div align="center"></div>
</td>
<td width="15%">
<div align="center"></div>
</td>
<td width="15%">
<div align="center"></div>
</td>
</tr>
<tr>
<td align=middle style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">3</span></div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td>
<div align="center"></div>
</td>
<td>
<div align="center"></div>
</td>
<td >
<div align="center"></div>
</td>
<td >
<div align="center"></div>
</td>
</tr>
<tr>
<td align=middle style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">5</span></div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center"> </div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td >
<div align="center"></div>
</td>
<td >
<div align="center"></div>
</td>
<td >
<div align="center"></div>
</td>
</tr>
<tr>
<td align=middle style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">6</span></div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td >
<div align="center"></div>
</td>
<td >
<div align="center"></div>
</td>
</tr>
<tr>
<td align=middle style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">7</span></div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td >
<div align="center"></div>
</td>
</tr>
<tr>
<td
style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center">ｑ<span class="down">8</span></div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center"> </div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
<td
style="BORDER-RIGHT: #000000 1px double; BORDER-TOP: #000000 1px double; BORDER-LEFT: #000000 1px double; BORDER-BOTTOM: #000000 1px double"
>
<div align="center">X</div>
</td>
</tr>
<tr>
<td align=right style="BORDER-RIGHT: #000000 0px double; BORDER-TOP: #000000 0px double; BORDER-LEFT: #000000 0px double; BORDER-BOTTOM: #000000 0px double"
>
<div align="center"></div>
</td>
<td>
<div align="center">ｑ<span class="down">1</span></div>
</td>
<td >
<div align="center">ｑ<span class="down">2</span></div>
</td>
<td >
<div align="center">ｑ<span class="down">3</span></div>
</td>
<td >
<div align="center">ｑ<span class="down">5</span></div>
</td>
<td>
<div align="center">ｑ<span class="down">6</span></div>
</td>
<td>
<div align="center">ｑ<span class="down">7</span></div>
</td>
</tr>
</table>
<p align="center"><br>
<IMG src="IMG/3.9.gif"> </p>
<br>
</p>
<div align=left><b>观看演示 </b><A href="program/test3_5/page1.htm" target=_new>确定的有限自动机的化简>></a><IMG src="../images/yanshi.gif" width="36" height="35"></div>
</td>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2a.htm'" src="../images/previous.gif" width="65" height="27"></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.1a.htm'" src="../images/next.gif" width="63" height="27"></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -