📄 2.2.2h.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>

<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.2.2g.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.2.2i.htm'"></img></td>
</tr>
</table>
<br><br>

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<p>
<font class="example">例2.4&nbsp</font>设G=(V<sub>T</sub>={a,b},V<sub>N</sub>={S,A,B},S,P}<br>
&nbsp&nbsp&nbsp&nbsp 其中P： <br>
&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp S→aB|bA <br>
&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp A→a|aS|bAA <br>
&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp B→b|bS|aBB <br>
&nbsp&nbsp&nbsp&nbsp文法G是上下文无关文法,语言L(G)={w|w∈{a,b}<sup>+</sup>,且w中有相同个数的a和b}。     
</p>
<p>
下面，用归纳法证明下面结论：<br>
&nbsp&nbsp&nbsp&nbsp (1)S <img src="IMG/equal.gif"></img> w,当且仅当w中含有相同个数的a和b。 <br>
&nbsp&nbsp&nbsp&nbsp (2)A <img src="IMG/equal.gif"></img> w,当且仅当w中a的个数比b的个数多一个。 <br>
&nbsp&nbsp&nbsp&nbsp (3)B <img src="IMG/equal.gif"></img> w,当且仅当w中b的个数比a的个数多一个。<br>
</p>
<p>
当|w|=1，A <img src="IMG/equal.gif"></img> a,B <img src="IMG/equal.gif"></img> b,不能从S导出长度为1的终极行,则上述结论显然成立。
</p>
<p>
设(1),(2)和(3)对于长度不超过k-1的所有w都成立。那么，证明对|w|=k也成立。对于(1),推导或者从S→aB开始,或者从S→bA开始。如果从S→aB开始，则S <img src="IMG/equal.gif"></img> aw1=w,其中B <img src="IMG/equal.gif"></img> w1,且|w1|=k-1。由假设,w1中b的个数比a的个数多一个,因此w中含有相同个数的a和b。同样可以证明，从S→bA出发，推导出的w中也含有相同个数的a和b。
</p>
<p>
下面证明，若|w|=k,且w中含相同个数的a和b,则S<img src="img\equalstar.gif"  width="20" height="23">w。     
</p>
<p>
w的第一个符号要么是a，要么是b。设w=aw<sub>1</sub>,|w<sub>1</sub>|=k-1,并且w<sub>1</sub>中b的个数比a多一个。由假设，B <img src="IMG/equal.gif"></img> w<sub>1</sub>,因此有S <img src="IMG/equal.gif"></img> aB <img src="IMG/equal.gif"></img> aw<sub>1</sub>=w。类似可以证明w开始为b的情形。
</p>
<p>
关于(2)和(3)的证明和(1)类似,证明过程留给读者。
</p>
</td></tr></table>

<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.2.2g.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='2.2.2i.htm'"></img></td>
</tr>
</table>

</BODY>
</html>
<html><script language="JavaScript">
⌨️ 快捷键说明

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