📄 arti_10691_4.htm
字号:
<P>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid black .75pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 8" align=center>{1}
<P>
<p></td></tr>
<tr style="HEIGHT: 14.35pt; mso-yfti-irow: 2; mso-yfti-lastrow: yes">
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 72pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid black .75pt" vAlign=top width=96>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 6" align=center>{1 }
<P>
<p></td>
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 73.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid black .75pt; mso-border-alt: solid black .75pt" vAlign=top width=98>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 2" align=center>{0,Y}
<P>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 10" align=center><B>Φ</B>
<P>
<p></td></tr></table></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">重命名的状态转换矩阵为:
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">
<table class=MsoTableGrid2 style="BORDER-RIGHT: medium none; BORDER-TOP: medium none; MARGIN-LEFT: 125.4pt; BORDER-LEFT: medium none; BORDER-BOTTOM: medium none; BORDER-COLLAPSE: collapse; mso-border-top-alt: solid windowtext .5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-yfti-tbllook: 480; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-border-insideh: .75pt solid black; mso-border-insidev: .75pt solid black" cellSpacing=0 cellPadding=0 border=1>
<tr style="HEIGHT: 14.35pt; mso-yfti-irow: -1; mso-yfti-firstrow: yes">
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 72pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid windowtext .5pt; mso-border-bottom-alt: solid black .75pt; mso-border-right-alt: solid black .75pt" vAlign=top width=96>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 5" align=center><B>状态
<P></B>
<p></td>
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 73.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid windowtext .5pt; mso-border-left-alt: solid black .75pt; mso-border-alt: solid black .75pt" vAlign=top width=98>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 1" align=center><B>I0
<P></B>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 1pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid windowtext .5pt; mso-border-bottom-alt: solid black .75pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 9" align=center><B>I1
<P></B>
<p></td></tr>
<tr style="HEIGHT: 15.05pt; mso-yfti-irow: 0">
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 72pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 15.05pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid black .75pt; mso-border-right-alt: solid black .75pt" vAlign=top width=96>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 4" align=center>0+-
<P>
<p></td>
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 73.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 15.05pt; mso-border-top-alt: solid black .75pt; mso-border-left-alt: solid black .75pt; mso-border-alt: solid black .75pt" vAlign=top width=98>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt" align=center>1
<P>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 15.05pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid black .75pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 8" align=center>2
<P>
<p></td></tr>
<tr style="HEIGHT: 14.35pt; mso-yfti-irow: 1">
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 72pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid black .75pt; mso-border-right-alt: solid black .75pt" vAlign=top width=96>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 4" align=center>1-
<P>
<p></td>
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 73.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-left-alt: solid black .75pt; mso-border-alt: solid black .75pt" vAlign=top width=98>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt" align=center>1
<P>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: black 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid black .75pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 8" align=center>2
<P>
<p></td></tr>
<tr style="HEIGHT: 14.35pt; mso-yfti-irow: 2; mso-yfti-lastrow: yes">
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 72pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid black .75pt" vAlign=top width=96>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 6" align=center>2
<P>
<p></td>
<td style="BORDER-RIGHT: black 1pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 73.4pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid black .75pt; mso-border-alt: solid black .75pt" vAlign=top width=98>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 2" align=center>1
<P>
<p></td>
<td style="BORDER-RIGHT: medium none; PADDING-RIGHT: 5.4pt; BORDER-TOP: medium none; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 62.6pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 1pt solid; HEIGHT: 14.35pt; mso-border-top-alt: solid black .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid black .75pt" vAlign=top width=83>
<P class=MsoNormal style="LINE-HEIGHT: 16pt; TEXT-ALIGN: center; mso-line-height-rule: exactly; tab-stops: 49.5pt; mso-yfti-cnfc: 10" align=center><B>Φ</B>
<P>
<p></td></tr></table></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">化简后的DFA为:<img src="http://10we.cn/article/UploadPic/2007-12/2007122518521953936.jpg" width=258 onclick="javascript:window.open(this.src);" style="CURSOR: pointer" onload="return imgzoom(this,550)">
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt"><v:shapetype id=_x0000_t202 coordsize="21600,21600" path="m,l,21600r21600,l21600,xe" spt="202"><v:stroke joinstyle="miter"></v:stroke><v:path gradientshapeok="t" connecttype="rect"></v:path></v:shapetype><v:shape id=_x0000_s1026 style="MARGIN-TOP: -217.5pt; Z-INDEX: 1; LEFT: 0px; MARGIN-LEFT: 172.25pt; WIDTH: 16pt; TEXT-INDENT: 0px; POSITION: absolute; HEIGHT: 25.5pt; TEXT-ALIGN: left" filled="f" stroked="f" type="#_x0000_t202"><v:textbox style="mso-next-textbox: #_x0000_s1026" inset="3mm,.3mm,,.3mm"></v:textbox></v:shape>
<table cellSpacing=0 cellPadding=0 width="100%">
<tr>
<td>
<div class=shape style="PADDING-RIGHT: 7.2pt; PADDING-LEFT: 8.503pt; PADDING-BOTTOM: 0.85pt; PADDING-TOP: 0.85pt" v:shape="_x0000_s1026">
<P class=MsoNormal>0</P>
<P class=MsoNormal>
<p></div></td></tr></table>第4步:对该确定化后的DFA进行最小化。
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">首先初始划分为:{0,1},{2}
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">考察{0,1}
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt"> {0,1}0={1} {0,1}1={2} 所以{0,1}不可再细分
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt"><v:shape id=_x0000_s1027 style="MARGIN-TOP: 8.75pt; Z-INDEX: 2; LEFT: 0px; MARGIN-LEFT: 112pt; WIDTH: 16pt; TEXT-INDENT: 0px; POSITION: absolute; HEIGHT: 25.5pt; TEXT-ALIGN: left" filled="f" stroked="f" type="#_x0000_t202"><v:textbox style="mso-next-textbox: #_x0000_s1027" inset="3mm,.3mm,,.3mm"></v:textbox></v:shape>
<table cellSpacing=0 cellPadding=0 width="100%">
<tr>
<td>
<div class=shape style="PADDING-RIGHT: 7.2pt; PADDING-LEFT: 8.503pt; PADDING-BOTTOM: 0.85pt; PADDING-TOP: 0.85pt" v:shape="_x0000_s1027"></div></td></tr></table>保留0,删除1后,得到化简后的DFA即为所求得的DFA。</P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt"></P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt">15.给定右线性文法G:
<P>
<P>
<P class=MsoNormal style="TEXT-INDENT: 21pt; LINE-HEIGHT: 16pt; mso-line-height-rule: exactly; tab-stops: 49.5pt"> S→0S|1S|1A|0B
<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -