📄 3.3.2b.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 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" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2c.htm'"src="../images/next.gif" ></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td width=30></td>
		<td>
			<p> 两个状态p和q等价满足下面条件：</p> 
			(a)<font color=red>一致性条件</font> <font class="emphasize">状态p和q必须同时或为接受状态或为非接受状态。</font> <br>       
			(b)<font color=red>蔓延性条件</font> <font class="emphasize">对于所有的a∈Σ,δ(p,a)=S,δ(q,a)=r,s和r必须等价。<font></font></font>       
		</td>
	</tr>
</table>
<table border=0>
	<tr>
		<td width=10></td>
		<td colspan=2>
			<br>
			<p>1.<font class="definition2">根据一致性条件</font>,因为终结状态有一条到达自身的ε-道路,而非终结状态没有到达终结状态的ε-道路,故它们是可区别的。在图3.8(b)中,我们把X放在下列表项中,(ｑ<sub>1</sub>,ｑ<sub>3</sub>),(ｑ<sub>2</sub>,ｑ<sub>3</sub>),(ｑ<sub>3</sub>,ｑ<sub>5</sub>),(ｑ<sub>3</sub>,ｑ<sub>6</sub>),(ｑ<sub>3</sub>,ｑ<sub>7</sub>),(ｑ<sub>3</sub>,ｑ<sub>8</sub>)。</p> 
			<p>2.<font class="definition2">根据蔓延性条件</font>,对每一个状态对(ｐ,ｑ),假定还不知道它们是否可区别,则对每一个输入符号ａ∈Σ考虑</p> 
			<p>ｒ＝δ(ｐ,ａ),ｓ＝δ(ｑ,ａ)</p> 
			<p>若对每一个ａ∈Σ,所对应的状态ｒ与ｓ均等价,则易知ｐ与ｑ等价。若存在某个ａ∈Σ使ｒ和ｓ可区别,则ｐ和ｑ可区别。这是因为,若ｒ与ｓ通过某ｗ∈Σ<sup>*</sup>已知道ｒ与ｓ是可区别的,则通过ａｗ可知ｐ和ｑ可区别。所以若表项(ｒ,ｓ)中有Ｘ,则Ｘ也可以放到表项(ｐ,ｑ)中。若表项(ｒ,ｓ)中还没有Ｘ,则将状态对(ｐ,ｑ)置入与(ｒ,ｓ)表项相关联的表中。等将来某个时刻,如果表项(ｒ,ｓ)获得一个Ｘ,那么与(ｒ,ｓ)表项相关联的表中的每个状态对也都将得到一个Ｘ。如图3.8(a)所示的DFAM中有一个输入符号1,使<BR>
			<center>(δ(ｑ<sub>2</sub>,1),δ(ｑ<sub>1</sub>,1))＝(ｑ<sub>3</sub>,ｑ<sub>6</sub>) </center>
			<br> 
			因表项(ｑ<sub>3</sub>,ｑ<sub>6</sub>)已有Ｘ,故在表项(ｑ<sub>1</sub>,ｑ<sub>2</sub>)中也放上一个Ｘ。  <br> 
			考虑表项(ｑ<sub>1</sub>,ｑ<sub>5</sub>),因为有一个输入符号O使  <br> 
			<center>(δ(ｑ<sub>1</sub>,0),δ(ｑ<sub>5</sub>,0))＝(ｑ<sub>2</sub>,ｑ<sub>8</sub>)</center><BR>
			这导致(ｑ<sub>1</sub>,ｑ<sub>5</sub>)被置入与(ｑ<sub>2</sub>,ｑ<sub>8</sub>)表项相关联的表中,但因为ｑ<sub>2</sub>与ｑ<sub>8</sub>等价,故不能推出ｑ1与ｑ5之间有什么肯定的结论。这时还必须考虑另外一个输入符号1,由于还有<br> 
			<center>(δ(ｑ<sub>１</sub>,1),δ(ｑ<sub>5</sub>,1))＝(ｑ<sub>6</sub>,ｑ<sub>6</sub>)</center> <br> 
			因此就可推出ｑ<sub>1</sub>与ｑ<sub>5</sub>等价。<br>
			考虑(ｑ<sub>1</sub>,ｑ<sub>7</sub>),由于对输入符号0有  <br> 
			<center>(δ(ｑ<sub>１</sub>,0),δ(ｑ<sub>7</sub>,0))＝(ｑ<sub>2</sub>,ｑ<sub>7</sub>)</center></p> 
			<p align="center"><IMG src="IMG/3.8.gif"></p> 
		</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" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.2c.htm'"src="../images/next.gif" ></td>
	</tr>
</table>
</BODY>
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -