📄 3.4.2c.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.4.2b.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2d.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td>
			<p><b>情况3</b>　r＝r<sub>1</sub><sup>*</sup>。r<sub>1</sub>的运算个数少于i，M<sub>1</sub>如情况1中所设，令:<br>
			  <center>M＝(Σ<sub>1</sub>，q<sub>1</sub>∪{q<sub>0</sub>，f<sub>0</sub>}，q<sub>0</sub>，{f<sub>0</sub>，δ}) </center><br>
			  其中q<sub>0</sub>和f<sub>0</sub>是不属于q<sub>1</sub>的新增加的二个不同的状态符号，转移函数δ定义如下： <br>
			<table>
				<tr>
					<td width=70> </td>
					<td>
						(a)δ(q<sub>0</sub>，ε)＝δ(f<sub>1</sub>，ε)＝{q<sub>1</sub>，f<sub>0</sub>}； 
						<br>
						(b)δ(q，a)＝δ<sub>1</sub>(q，a)，　当q∈q<sub>1</sub>－{f<sub>1</sub>}，a∈Σ<sub>1</sub>∪{ε} 
					</td>
				</tr>
			</table>
			  M的状态转换如图3.11(c)所示，显然M中任何一条从q<sub>0</sub>到f<sub>0</sub>的路径，或者是一条从q<sub>0</sub>到f<sub>0</sub>的经过箭弧标记为ε的路径，或者首先是一条从q<sub>0</sub>到q<sub>1</sub>的ε－道路，接着的是若干条(包括零条)标记为L(M)中的一个符号串，从q<sub>1</sub>到f<sub>1</sub>，然后是经过箭弧ε折回q<sub>1</sub>的道路。最后接着是一条标记为L(M<sub>1</sub>)中的一个符号串，从q<sub>1</sub>到f<sub>1</sub>，再经过标记为ε的箭弧到达f<sub>0</sub>的路径。因此M中有一条从q<sub>0</sub>到f<sub>0</sub>的道路w当且仅当我们能够将w写成 <br>
			  <center>w＝x<sub>1</sub>x<sub>2</sub>…x<sub>k</sub>，(k≥0，k＝0意味着w＝ε) </center><br>
			  其中x<sub>i</sub>∈L(M<sub>1</sub>)，i＝1，2，…，k。所以 <br>
			  <center>L(M)＝L(M<sub>1</sub>)<sup>*</sup>＝L(r<sub>1</sub>)<sup>*</sup>＝L(r) </center><br>
			  <p>定理3.2第二部分的证明,对于Σ上任一NFAM,能构造Σ上一个正规表达式r，使得L(r)=L(M)。我们把转换图的概念拓广，每条弧上可以用一个正规表达式标记。首先，在M的转换图上加进两个结，一个为X，另一个为Y，从X用ε弧连接到M的所有初态节点，从M的所有接受状态结用ε弧连接到Y从而构成一个新的NFAM'，显然L(M')=L(M)。下面，我们逐步消去M'中的所有状态节点，直到只剩下X和Y为止。在消结的过程中，逐步用正规表达式标记弧，消结的过程是直现的，只需反复使用图3.12的替换规则。</p>    
			<p align="center"><img src="IMG/3.12.gif" width="437" height="265"></p>
			<p>定理3.2的证明，实质上是将一个正规表达式变成一个有限自动机的算法，不过这个算法是隐含地假定了正规表达式是完全用括号括好了的。对于没有多余括号的正规表达式，我们还必须确定正规表达式究竟是r|ｓ形式，还是rｓ形式，还是r<sup>*</sup>形式。这等价于在上下文无关文法中对一个符号串进行语法分析。 </p>
		</td>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2b.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2d.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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