📄 3.5.1b.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.5.1a.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1c.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td>
			<p><IMG src="img/dingli.gif"><b>定理3．4&nbsp;</b><font class="dingli">对每一个DFA M,都存在一个右线性正规文法G和一个左线性正规文法G',使L(M)＝L(G)＝L(G')</font></p> 
			  <p><b>证</b>&nbsp;&nbsp;&nbsp;&nbsp;设DFA M＝(Σ,V<sub>N</sub>,S,f,δ),其中V<sub>N</sub>是状态集,它的元素在本定理证明中临时用大写英文字母表示,因为当我们从M出发构造与之等价的正规文法G时,我们是把V<sub>N</sub>中的状态符号看成G中的非终结符号,而在正规文法的定义中,我们曾经约定过,非终结符号要用大写英文字母表示。   
			    <br> 
			    若初态符号S<IMG src="IMG\notbelong.gif">f,我们令<br>
				<table>
					<tr>
						<td width=70> </td>
						<td>
					      　G＝(Σ,V<sub>N</sub>,S,P) <br>
						</td>
					</tr>
				</table><br>
			    其中Σ的元素为终结符号,V<sub>N</sub>的元素为非终结符号,P按下面规则定义的产生式集合。 <br>
			    对任何a∈Σ及A,B∈VN,若有δ(A,a)＝B,则 <br>
			    (a)当B<IMG src="IMG\notbelong.gif">f时,令A→aB。 <br>
			    (b)当B∈f时,令A→a|aB。 <br>
			    在第2种情况下之所以规定A→a|aB,这是因为DFA M中可能有从状态B到自身的转移,而且还可能有从状态B到另一些状态的转移。 <br>  
			    对任何w∈Σ<sup>*</sup>,记w＝a<sub>1</sub>a<sub>2</sub>…a<sub>n</sub>,其中a<sub>i</sub>∈Σ(i＝1,2,…n)。若　S<img src="img/equal.gif"> w,则存在一个最左推导：<br>
				<table>
					<tr>
						<td width=70> </td>
						<td>
							S<img src="img/equal.gif">a<sub>1</sub>A<sub>1</sub><img src="img/equal.gif">a<sub>1</sub>a<sub>2</sub>A<sub>2</sub><img src="img/equal.gif">…<img src="img/equal.gif">a<sub>1</sub>a<sub>2</sub>…a<sub>i</sub>A<sub>i</sub><img src="img/equal.gif">…<img src="img/equal.gif">a<sub>1</sub>a<sub>2</sub>…a<sub>n</sub> 
						</td>
					</tr>
				</table><br>
			    因而在M中有一条从S出发依次经过A<sub>1</sub>,A<sub>2</sub>,…,A<sub>n-1</sub>再到达终态的箭弧标记依次为a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>,的道路,这条路上箭弧的标记符号依次连接恰好是w,反之亦然。因而w∈L(M)当且仅当w∈L(G)。若初态符号S∈f,因为δ(S,ε)＝S,所以ε∈L(M),但ε不属于上面构造的6所产生的语言L(G)。实际上L(G)＝L(M)—{ε}因而我们只要对上面由M出发所构造的右线性正规文法G中添加一个新的非终结符号S<sub>0</sub><IMG src="IMG\notbelong.gif">VN和产生式S<sub>0</sub>→S|ε,并用S<sub>0</sub>代替S作开始符号。这样经过修正后的G仍是右线性正规文法且L(G)＝L(M)。类似地从M出发可构造左线性正规文法G使L(G')=L(M)</p>
			<p>这部分的证明留给读者。</p>
			<p>由DFA,NFA和具有ε－转移的NFA之间的等价性,立刻得到定理3．3及定理3．4的二个推论。</p>
			<p><img src="img/dingli.gif"><b>推论1</b>&nbsp;&nbsp;&nbsp;&nbsp;<font class="dingli">对任何一个FA M,都存在一个正规文法G使L(G)＝L(M),反之亦然。因而FA所识别的语言是正规语言。</font><p>
			<p><img src="img/dingli.gif"><b>推论2</b>&nbsp;&nbsp;&nbsp;&nbsp;<font class="dingli">对任何一个右线性正规文法G都存在一个左线性正规文法G',使L(G')＝L(G),反之亦然。</font></p> 
		</td>
	</tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1a.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1c.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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