📄 3.3.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.3.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1c.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td colspan=2>
			<p>
				<img class="dingyi" src="img/dingli.gif"> 
				<b>定理3，1</b>&nbsp;&nbsp;&nbsp;&nbsp;对任何一个NFA M，都存在一个DFA M’，使</p>      
			<p>&nbsp&nbsp&nbsp&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp&nbsp&nbsp&nbsp;Ｌ（Ｍ’）＝Ｌ（Ｍ）</p>  
			<p>&nbsp;&nbsp;&nbsp;&nbsp;证明的基本思想是由M出发构造等价的M’，办法是让M’的状态对应于M的状态集合。即若δ（q,a)={ｑ<sub>１</sub>，．．．，ｑ<sub>ｋ</sub>},则把{ｑ<sub>１</sub>，．．．，ｑ<sub>ｋ</sub>}作为一个整体看作M＇中的一个状态，即Q’中一个元素。这里给出一个从DFAM构造DFAM’的算法，下面举例说明。</p>  
			<p>
				<img class="dingyi" src="img/liti.gif">
				 <b>例3.2 </b>设NFA M=（{0，1}，{ｑ<sub>0</sub>，ｑ<sub>１</sub>}，ｑ<sub>0</sub>，｛ｑ<sub>１</sub>｝，δ），其中：    
			</p>      
			<p align="center">δ（ｑ<sub>0</sub>,0)={ｑ<sub>0</sub>，ｑ<sub>１</sub>}，δ（ｑ<sub>0</sub>,１)=｛ｑ<sub>１</sub>}<br>
                       <p align="center">δ（ｑ<sub>１</sub>,0)=Φ，δ（ｑ<sub>１</sub>,１)={ｑ<sub>0</sub>，ｑ<sub>１</sub>}  
			</p> 
			<p> 其中</p>
		</td>
	</tr>
	<tr>
		<td></td>
		<td colspan=2>
			<table>	
				<tr>
					<td width=50></td>
					<td> 
						<b>(ａ)</b>把Q中一切子集组成的集合作为M'的状态的集合Q'。<br>
						&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 此例中Q'={Φ，{ｑ<sub>0</sub>}，｛ｑ<sub>１</sub>｝，{ｑ<sub>0</sub>，ｑ<sub>１</sub>}}<br>     
						<b>(ｂ)</b>ｑ<sub>0</sub>’＝｛ｑ<sub>0</sub>｝ <br>
						<b>(ｃ)</b>Ｍ’的终态集合Ｆ’是Ｑ子集中一切包含Ｆ中元素的集合所组成。<br>
						&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;此例中Ｆ’＝｛｛ｑ<sub>１</sub>｝，｛ｑ<sub>0</sub>，ｑ<sub>１</sub>｝｝      
						  <br> 
						<b>(ｄ)</b> δ’（｛ｑ<sub>１</sub>，ｑ<sub>２</sub>，．．．，ｑ<sub>ｋ</sub>｝，ａ）<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;＝δ（ｑ<sub>１</sub>，ａ）∪δ（ｑ<sub>2</sub>,ａ）∪．．．∪δ（ｑ<sub>ｋ</sub>，ａ）,<br>
						&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;在此例中<br>
						<table width="100%">
							<tr>
								<td>
									δ'(Φ,0)=Φ<br>
									δ'({q<sub>0</sub>},0)=δ(q<sub>0</sub>,0)={q<sub>0</sub>,q<sub>1</sub>}<br>
									δ'({q<sub>1</sub>},0)=δ(q<sub>1</sub>,0)=Φ<br>								
									δ'({q<sub>0</sub>,q<sub>1</sub>},0)<br>
&nbsp;&nbsp;&nbsp;=δ(q<sub>0</sub>,0)∪δ(q<sub>1</sub>,0)<br>
									&nbsp;&nbsp;&nbsp;={q<sub>0</sub>,q<sub>1</sub>}={q<sub>0</sub>,q<sub>1</sub>}&nbsp;<br>
								</td>
								<td>
									δ'(Φ,1)=Φ<br>
									δ'({q<sub>0</sub>},1)=δ'(q<sub>0</sub>,1)={q<sub>1</sub>},<br>
									δ'({q<sub>1</sub>},1)=δ(q<sub>1</sub>,1)={q<sub>0</sub>,q<sub>1</sub>},<br>    
									δ'({q<sub>0</sub>,q<sub>1</sub>},1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=δ(q<sub>0</sub>,1)∪(q<sub>1</sub>,1)<br>
									&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;={q<sub>1</sub>}{q<sub>0</sub>,q<sub>1</sub>}={q<sub>0</sub>,q<sub>1</sub>} <br> 
								</td>
							</tr>
						</table>
					</td>
				</tr>
			</table>
		</td>
	</tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1c.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 + -