📄 3.4.2a.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.1e.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2b.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=5></td>
		<td>
			<br>
			<b>3.4.2 正规表达式与有限自动机的等价性</b><br><br>    
		</td>
	</tr>
	<tr>
		<td width=10></td>
		<td>
			  <p>为构造词法分析器，我们要构造一个最小化的 DFA M，使得M接受程序语言的单词，然后我们可以用程序模拟 DFA M，得到词法分析器。我们知道，用正规表达式，可以方便的描述程序语言的单词，而在正规表达式和 FA M之间，存在一转换算法，对于任一正规表达式r，都能构造一个 FA M，使得L(M)=L(r)，这样，从正规表达式就能用程序构造出与之等价的最小化的 DFA M，为此，证明下面的定理：     
			    <br>
			    <br>
			    <b><img src="img/dingli.gif">定理3.2</b> <font class="dingli">设r是Σ上一个正规表达式，则存在一个FAM接受L(r)。反之亦然。</font><br>    
			    <br>
			    <b>证:</b>　我们将证明存在一个具有ε－转移的NFA　M，M只有一个终结状态，而且没有从这个终结状态出去的转移，使</p>
			<p><center>L(M)＝L(r)</center></p>
			<p>注意，这里实际上要证明的结论比定理中叙述的结论要强些。下面将用关于正规表达式r中运算数目的归纳法证明这个结论成立。若r具有零个运算，则或r＝ε；或r＝Φ或r＝a∈Σ，此时图3.10(a)，(b)和(c)所示的三个有限自动机显然满足我们所要求的结论。</p>
			<p align="center"><img src="IMG/3.10.gif" width="456" height="121"><br>
			</p>
			<p>假设结论对于少于i(i≥1)个运算的正规表达式成立。当r有i个运算时，据正规表达式定义，r的形式有三种情况，我们分情况证明。 </p>
			<p> <b>情况1</b>　　r＝r<sub>1</sub>|r<sub>2</sub>。　r<sub>1</sub>和r<sub>2</sub>的运算个数少于i，于是根据归纳法的假设，对r<sub>1</sub>及r<sub>2</sub>分别存在 <br>
			<center>  M<sub>1</sub>＝(Σ<sub>1</sub>，q<sub>1</sub>，q<sub>1</sub>，{f<sub>1</sub>}，δ<sub>1</sub>)  <br>
			  M<sub>2</sub>＝(Σ<sub>2</sub>，q<sub>2</sub>，q<sub>2</sub>，{f<sub>2</sub>}，δ<sub>2</sub>)<br>
			</center> 
			  
			  使得L(M<sub>1</sub>)＝L(r<sub>1</sub>)，L(M<sub>2</sub>)＝L(r<sub>2</sub>)。其中M<sub>1</sub>与M<sub>2</sub>都没有从终结状态出去的转移。因为我们可随意给有限自动机的状态命名，故可设q<sub>1</sub>∩q<sub>2</sub>＝Φ。在集合q<sub>1</sub>∪q<sub>2</sub>中加进两个新的状态符号q<sub>0</sub>及f<sub>0</sub>，分别作为下面有限自动机的初态和终态，令 <br>
			  <center>M＝(Σ<sub>1</sub>∪Σ<sub>2</sub>，q<sub>1</sub>∪q<sub>2</sub>∪{q<sub>0</sub>，f<sub>0</sub>}，q<sub>0</sub>，{f<sub>0</sub>}，δ) </center>			  <br>
			  其中δ定义如下： <br>
			  <table>
				<tr>
					<td width=70> </td>
					<td>
						(a)δ(q<sub>0</sub>，ε)＝{q<sub>1</sub>，q<sub>2</sub>} <br>
						(b)δ(q，a)＝δ<sub>1</sub>(q，a)，　当q∈q<sub>1</sub>－{f<sub>1</sub>}，a∈Σ<sub>1</sub>∪{ε} <br>
						(c)δ(q，a)＝δ<sub>2</sub>(q，a)，　当q∈q<sub>2</sub>－{f<sub>2</sub>}，a∈Σ<sub>2</sub>∪{ε}<br>
						(d)δ(f<sub>1</sub>，ε)＝δ<sub>1</sub>(f<sub>2</sub>，ε)＝{f<sub>0</sub>}
					</td>
				</tr>
			</table>
			<p>M的状态转换如图3.11(a)所示。在M的状态转换图中，任何一条由q<sub>0</sub>到f<sub>0</sub>的道路，开始时都必须经过ε箭弧而到达q<sub>1</sub>或q<sub>2</sub>。如果到达q<sub>1</sub>，它就可以沿着M<sub>1</sub>的任何路径到达f<sub>1</sub>，然后再经过ε箭弧到达f<sub>0</sub>，如果开始到达q<sub>2</sub>，它就可以沿着M<sub>2</sub>的任何路径到达f<sub>2</sub>，然后再经过ε箭弧到达f<sub>0</sub>。这些就是从q<sub>0</sub>到达f<sub>0</sub>仅有的一些路径，所以M中有一条从q<sub>0</sub>到f<sub>0</sub>的道路w当且仅当或在M<sub>1</sub>中有一条从q<sub>1</sub>到f<sub>1</sub>的道路w或在M<sub>2</sub>中有一条从q<sub>2</sub>到f<sub>0</sub>的道路w。故: <br>
			  <center>L(M)＝L(M<sub>1</sub>)∪L(M<sub>2</sub>)＝L(r<sub>1</sub>)∪L(r<sub>2</sub>)＝L(r)</center> 
			</p>
		</td>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.1e.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2b.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 + -