📄 3.2.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.2.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.1c.htm'" src="../images/next.gif"></IMG></td>
	</tr>
</table>
<br><br>
<table border=0>
	<tr>
		<td width=10></td>
		<td colspan=2>
			<p>通过前面对奇偶检验器的设计，下面给出确定的有限自动机的定义。 </p>
				<img class="dingyi" src="../images/dingyi.gif"></img>
				<font size=5><b>定义3．1</b></font>
				</font>&nbsp;&nbsp;一个<font class="definition2">确定的有限自动机</font>M（记作DFAM）是一个五元组
			<p align="center">M＝（Σ，Q，q<sub>0</sub>，F，δ）</p> 
			其中
		</td>
	</tr>
	<tr>
		<td width=10></td>
		<td width=30></td>
		<td>
			(a) Q是一个有限状态集合。 <br> 
			(b) Σ是一个字母表，它的每个元素称为一个输入符号。 <br> 
			(c) q<sub>0</sub>∈Q，q<sub>0</sub>称为初始状态。 <br> 
			(d) F∈Q，F称为终结状态集合。 <br> 
			(e) δ是一个从Q×S到Q的单值映射：
			  
			<p >&nbsp;&nbsp;&nbsp;&nbsp;δ(q,a)＝q'　　(q,q'∈Q，a∈Σ）</p>
		</td>
	</tr>
	<tr>
		<td></td>
		<td colspan=2>
			<p>表示当前状态为q，输入符号为a时，自动机将转换到下一个状态q'，q'称为q的一个<font color=red>后继</font>。</p>
			<p>若Q＝{q<sub>1</sub>,q<sub>2</sub>, ... q<sub>n</sub>}，Σ＝{a<sub>1</sub>,a<sub>2</sub>, ... ,a<sub>m</sub>}则</p>
			<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(δ(q<sub>i</sub>,a<sub>j</sub>))<sub>nｘm</sub></p>
			<p>是一个n行m列矩阵，它称为DFA M的<font color=red>状态转换矩阵</font>，或称<font color=red>转换表</font>。</p> 
		</td>
	<tr>
	<tr>
		<td width=10></td>
		<td colspan=2>
			<p><IMG class=dingyi src="img/liti.gif" width="32" height="31"> 
			<font size=5><b>例3.1</b></font>&nbsp;设DFA M＝( { a , b } , { 0 , 1 , 2 , 3 } , 0 , { 3 } ,δ )其中</p>    
			<p>δ( 0 , a ) = 1,&nbsp;δ( 1 , a ) = 3,&nbsp;δ( 2 , a ) = 1,&nbsp;δ( 3 , a ) = 3</p>   
			<p>δ( 0 , b ) = 2,&nbsp;δ( 1 , b ) = 2,&nbsp;δ( 2 , b ) = 3,&nbsp;δ( 3 , b ) = 3</p>   
			<p>则M的状态转换矩阵为</p>
			<table width="75%" border="1" align="center" cellspacing="0" cellpadding="3">
			  <tr> 
			    <td rowspan=2> 
			      <div align="center">状态</div>
			    </td>
			    <td colspan=2 align=middle>输入符号</td>
			  <tr> 
			    <td> 
			      <div align="center">a</div>
			    </td>
			    <td> 
			      <div align="center">b</div>
			    </td>
			  </tr>
			  <tr> 
			    <td> 
			      <div align="center">0</div>
			    </td>
			    <td> 
			      <div align="center">1</div>
			    </td>
			    <td> 
			      <div align="center">2</div>
			    </td>
			  </tr>
			  <tr> 
			    <td> 
			      <div align="center">1</div>
			    </td>
			    <td> 
			      <div align="center">3</div>
			    </td>
			    <td> 
			      <div align="center">2</div>
			    </td>
			  </tr>
			  <tr> 
			    <td> 
			      <div align="center">2</div>
			    </td>
			    <td> 
			      <div align="center">1</div>
			    </td>
			    <td> 
			      <div align="center">3</div>
			    </td>
			  </tr>
			  <tr> 
			    <td> 
			      <div align="center">3</div>
			    </td>
			    <td> 
			      <div align="center">3</div>
			    </td>
			    <td> 
			      <div align="center">3</div>
			    </td>
			  </tr>
			</table>
			<p>
			  一个确定的有限自动机M可以形象地通过一张状态转换图来表示，假定M有ｎ个状态，ｍ个输入符号，那么这个状态转换图含有n个状态结，每个状态结最多有ｍ条箭弧射出与别的状态结相连接，准确他说，若转移函数对于ｑ，ｑ’∈Ｑ，ａ∈Σ有δ（ｑ，ａ）＝ｑ’则从ｑ到ｑ’有一条标记为ａ的箭弧。整个图含有唯一一个初态结和若干个终态结（可以是0个）。</p>
		</td>
	</tr>
</table>
<table align=right width=300>
	<tr>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.1a.htm'" src="../images/previous.gif"></IMG></td>
		<td><IMG onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='3.2.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 + -