📄 3.5.1a.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.2d.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1b.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td colspan=2>
			<font class="title2"><b>3.5 正规文法与有限自动机(FA)的等价性</b></font>    
		</td>
	</tr>
	<tr>
		<td width=10></td>
		<td>
			<p>在我们引入有限自动机概念时,我们已清楚地看到正规文法G所用以识别句子的状态转换图就是某个有限自动机的状态转换图。这就是说正规文法G所产生的语言和某个有限自动机所识别的语言是相同的。  <br> 
			  &nbsp;&nbsp;&nbsp;&nbsp;如果对于某个正规文法G和某个有限自动机M有L(G)＝L(M),则称G和M是<font class="definition3">等价的</font>,关于正规文法和有限自动机的等价性,我们有如下两个定理。</p> 
			  <p><IMG src="img/dingli.gif"><b>定理3.3  </b><font class="dingli">对每一个右线性正规文法G或左线性正规文法G,都存在一个FA M,使L(M)＝L(G)。</font>	<br>
			  <br>
			<b>证:</b>  设给定了一个右线性正规文法: G＝(V<sub>T</sub>,V<sub>N</sub>,S,P),我们将V<sub>N</sub>中的每一个非终结符号看作一个状态符号,并增加一个终结状态符号f且f<IMG src="IMG/notbelong.gif" >V<sub>N</sub>,令:&nbsp;     
				<table>
					<tr>
						<td width=70> </td>
						<td>
							M＝(V<sub>T</sub>,q,S,f,δ)
						</td>
					</tr>
				</table>
			    其中q＝V<sub>N</sub>∪{f},f＝{f},转移函数δ按下述规则定义： <br>
				<table>
					<tr>
						<td width=70> </td>
						<td>
							(A)若对某个A∈V<sub>N</sub>及a∈V<sub>T</sub>∪{ε},P中有产生式A→a,则令δ(A,A)＝f <br>
							(B)对任何给定的A∈V<sub>N</sub>及a∈V<sub>T</sub>∪{ε},设产生式集合P中左端为A,右端第一符号为a的所有产生式为: <br>
							<center>A→aA<sub>1</sub>|aA<sub>2</sub>|…|aA<sub>k</sub>,(不包括A→a)则令δ(A,a)＝{A<sub>1</sub>,A<sub>2</sub>,…,A<sub>k</sub>}</center>
						</td>
					</tr>
				</table>
				显然,这样构造的M是一个具有ε－转移的NFA。又因为对右线性正规文法G在S<IMG src="IMG/deduce.gif">w的最左推导过程中,若利用A→aB一次就相当于在M中从状态A经过标记为A(包括a＝ε)的箭弧到达状态B。在推导的最后,利用A→a一次就相当于在M中从A出发经过标记为a(包括a＝ε)的箭弧到达终结状态f,这就是说在正规文法G中,S<IMG src="IMG/deduce.gif">w的充分必要条件是：从状态S到状态f有一条道路,这条路上所有箭弧的标记符号依次连接起来正好等于w,。故w∈L(G)的充分必要条件是w∈L(M)。所以<b>L(G)＝L(M)</b>。<br>
			  <p>设给定了一个左线性正规文法: G＝(V<sub>T</sub>,V<sub>N</sub>,S,P),我们将V<sub>N</sub>的每一个符号看成一个状态符号并将文法G的开始符号看成终结状态符号,再增加一个初始状态符号q<sub>0</sub>且q<sub>0</sub><IMG height=16 src="IMG/notbelong.gif" width=10>V<sub>N</sub>。令:&nbsp;   
				<table>
					<tr>
						<td width=70> </td>
						<td>
							M'＝(V<sub>T</sub>,q,q<sub>0</sub>,{S},δ) 
						</td>
					</tr>
				</table>
			    其中q＝V<sub>N</sub>∪{q<sub>0</sub>},转移函数δ按下述办法定义： 
				<table>
					<tr>
						<td width=70> </td>
						<td>
							(a)若对某个A∈V<sub>N</sub>及a∈V<sub>T</sub>∪{ε},P中有产生式A→a,则令δ(q<sub>0</sub>,a)＝A。<br>
							(b)对任何A∈V<sub>N</sub>及a∈V<sub>T</sub>∪{ε},若P中所有右端第一个符号为A第二个符号为a的产生式为A<sub>1</sub>→Aa,A<sub>2</sub>→Aa,…,A<sub>k</sub>→Aa,则令δ(A,a)＝(A<sub>1</sub>,A<sub>2</sub>,…,A<sub>k</sub>}。 
						</td>
					</tr>
				</table>
			    与右线性正规文法一样可类似地证明L(M')＝L(G)。</p>
			  <!--div align=left><b>观看演示 </b><font color=blue onmouseover="javascript:style.cursor='hand';" onclick="javascript:open('program/autogen/autogen.html','_blank','left=100,top=100,scrollbars=yes,resizable=yes,width=800,height=600')">根据正规表达式生成NFA、DFA、最简DFA</font><IMG src="../images/yanshi.gif"></div-->
		</td>
	</tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.4.2d.htm'" src="../images/previous.gif" ></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.5.1b.htm'" src="../images/next.gif" ></td>
	</tr>
</table>
</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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