📄 3.3.2a.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.1e.htm'" src="../images/previous.gif" ></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2b.htm'" src="../images/next.gif" ></td>
</tr>
</table>
<br><br>
<table border=0>
<tr>
<td width=5></td>
<td colspan=2>
<br>
<b>3.3.2 确定有限自动机的化简</b><br><br>
</td>
</tr>
<tr>
<td width=10></td>
<td width=30></td>
<td>
<p> 在图3.7(b)所示的DFA M状态转换图中,状态q<sub>4</sub>,q<sub>5</sub>,q<sub>6</sub>和q<sub>7</sub>都接受同样的输入串,因此可以选一个状态作为它们的代表，比如q<sub>4</sub>，然后，我们把到q<sub>5</sub>,q<sub>6</sub>和q<sub>7</sub>的转换都转换到状态q<sub>4</sub>，显然,可以去掉q<sub>5</sub>,q<sub>6</sub>和q<sub>7</sub>这几个状态,从而得到图3.7(a)。另外，在图3.8(a)所示的DFA M的状态转换图中，没有从q<sub>1</sub>到q<sub>4</sub>的转移，所以，q<sub>4</sub>是无用状态，故可以去掉q<sub>5</sub>及其射出的弧，从而得到与之等价的态转换图图3.8(b)。实际上任何一个含有ｎ个状态的DFA,都有含有ｍ(ｍ<=ｎ)个状态的DFA与之等价。如图3.7(a)与3.7(b)所示的两个DFA是等价的,它们所对应的正规表达是(a｜b)<sup>*</sup>(aa｜bb)(a｜b)<sup>*</sup>。显然3.7(a)比3.7(b)简化。</p>
<p align="center"> <IMG src="img/3.7.gif"></p>
<p>所谓一个<font class="definition2">DFA M＝(Σ,Q,q<sub>0</sub>,F,δ)的化简</font>是指寻找一个状态数比较少的DFA M',使L(M)＝L(M'),而且可以证明存在一个最少状态的DFA M'使L(M) = L(M')。</p>
<p>设p , q ∈ Q。若对任何w∈Σ<sup>*</sup>,δ(p , w) ∈ F 当且仅当δ( q , w ) ∈ F,则称状态p和q是<font class="emphasize">等价</font>的。如果p和q不等价,则称p , q是<font class="emphasize">可区别</font>的。 </p>
<p><font class="definition2">DFA M的最小化过程</font>,是把M的状态集Q分割成一些互不相交的予集,使得每个子集中任何两个状态是等价的,而任何两个属于不同子集的状态都是可区别的。然后在每个子集中任取一个状态做“代表”,而删去子集中其余状态,并把射向其余状态结的箭弧都改作射向这个做“代表”的状态结中。这样得到的状态转换图所对应的DFA M',就是接受Ｌ(Ｍ)的具有最少状态的DFA。<br>
至于如何把状态集Ｑ＝｛ｑ<sub>1</sub>,ｑ<sub>2</sub>,．．．,ｑ<sub>ｎ</sub>｝分割成具有所要求性质的互不相交的子集,因为终结状态有一条到达自身的ε-道路,而非终态结没有到达终态结的ε－道路,故它们是可区别的。在图3.8(a)所示的DFA中,我们把Ｘ放在下列表项中：
(q<sub>1</sub>,q<sub>3</sub>),(q<sub>2</sub>,q<sub>3</sub>),(q<sub>3</sub>,q<sub>4</sub>),(q<sub>3</sub>,q<sub>5</sub>),(q<sub>3</sub>,q<sub>6</sub>),(q<sub>3</sub>,q<sub>7</sub>),(q<sub>3</sub>,q<sub>8</sub>),如表3．3所示。</p>
</td>
</tr>
</table>
<table align=right width=300>
<tr>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1e.htm'" src="../images/previous.gif" ></td>
<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2b.htm'" src="../images/next.gif" ></td>
</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -