📄 3.3.1d.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.1c.htm'" src="../images/previous.gif"></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.13.htm'" src="../images/next.gif"></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td colspan=2>
			<p>
				<img class="dingyi" src="img/dingyi.gif" width="32" height="31">
				<b>例3.3</b> 对图3.6（a）的具有ε-转移的NFA，让我们来构造与之等价的DFA。    
			</p>  
			<center> <img src="IMG/3.6.gif"></center>  
			  <p>图3.6（a）中NFA接受(a|b)<sup>*</sup>abb。我们用abb模拟它的动作。开始在状态0，在这点上，NFA可以从{0，1，2，4，7}中任意一个出发，即，我们要计算ε-closure(0),它是从状态0出法，沿ε弧到达的所有状态。显然，在不读进第一个字母a的情况下，不可能到达其他状态。</p>  
			<p>下面做第一个a的转换，在{0，1，2，4，7}中，只有从2到达3，从7到达8，因此有{3，8}。但只要计算ε-closure(3)：从3沿ε弧可到达6，7，1，2，4。因此NFA必须在{1，2，3，4，6，7，8}中之一的状态。</p>  
			<p>接着，对a后的第一个b进行转换，从4状态到5状态，而从1，2，3，6，7没有转换，因此有状态集{5，9}，求它的ε-closure，得到{1，2，4，5，6，7，9}。</p>  
			<p>最后对第二个b做转换，从4状态到5状态，从9状态到10状态，从1，2，5，6，7状态没有转移，我们有集合{5，10}，它的ε-closure是{1，2，4，5，6，7，10}</p>  
			<p>现在，到达了串abb的尾部，集合{1，2，4，5，6，7，10}中的状态10是NFA的接受状态。因此，abb是图3.6（a）的NFA接受的字符串。</p>  
		</td>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1c.htm'" src="../images/previous.gif"></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.3.1e.htm'" src="../images/next.gif"></td>
	</tr>
</table>
</BODY>
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C

搜索代码 Ctrl + F

全屏模式 F11

切换主题 Ctrl + Shift + D

显示快捷键 ?

增大字号 Ctrl + =

减小字号 Ctrl + -