⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 编译原理-课后习题.doc

📁 编译原理-课后习题.rar
💻 DOC
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://202.117.80.9/jp2004/05/kcwz/stk/khxt/a3.htm -->
<html xmlns:v="urn:schemas-microsoft-com:vml"
xmlns:o="urn:schemas-microsoft-com:office:office"
xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=GB2312">
<meta name=ProgId content=Word.Document>
<meta name=Generator content="Microsoft Word 9">
<meta name=Originator content="Microsoft Word 9">
<link rel=File-List href="./编译原理-课后习题.files/filelist.xml">
<link rel=Edit-Time-Data href="./编译原理-课后习题.files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>编译原理-课后习题</title>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>zys</o:Author>
  <o:LastAuthor>zys</o:LastAuthor>
  <o:Revision>2</o:Revision>
  <o:TotalTime>0</o:TotalTime>
  <o:Created>2005-03-16T09:32:00Z</o:Created>
  <o:LastSaved>2005-03-16T09:32:00Z</o:LastSaved>
  <o:Pages>11</o:Pages>
  <o:Words>861</o:Words>
  <o:Characters>4912</o:Characters>
  <o:Company>workgroup</o:Company>
  <o:Lines>40</o:Lines>
  <o:Paragraphs>9</o:Paragraphs>
  <o:CharactersWithSpaces>6032</o:CharactersWithSpaces>
  <o:Version>9.2812</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
  <w:Compatibility>
   <w:UseFELayout/>
  </w:Compatibility>
 </w:WordDocument>
</xml><![endif]-->
<style>
<!--
 /* Font Definitions */
@font-face
	{font-family:Wingdings;
	panose-1:5 0 0 0 0 0 0 0 0 0;
	mso-font-charset:2;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:0 268435456 0 0 -2147483648 0;}
@font-face
	{font-family:宋体;
	panose-1:2 1 6 0 3 1 1 1 1 1;
	mso-font-alt:SimSun;
	mso-font-charset:134;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:3 135135232 16 0 262145 0;}
@font-face
	{font-family:黑体;
	panose-1:2 1 6 0 3 1 1 1 1 1;
	mso-font-alt:SimHei;
	mso-font-charset:134;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:1 135135232 16 0 262144 0;}
@font-face
	{font-family:"\@黑体";
	panose-1:2 1 6 0 3 1 1 1 1 1;
	mso-font-charset:134;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:1 135135232 16 0 262144 0;}
@font-face
	{font-family:"\@宋体";
	panose-1:2 1 6 0 3 1 1 1 1 1;
	mso-font-charset:134;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:3 135135232 16 0 262145 0;}
 /* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0cm;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:宋体;
	mso-bidi-font-family:"Times New Roman";}
p
	{font-size:12.0pt;
	font-family:宋体;
	mso-bidi-font-family:"Times New Roman";}
p.style1, li.style1, div.style1
	{mso-style-name:style1;
	margin-right:0cm;
	mso-margin-top-alt:auto;
	mso-margin-bottom-alt:auto;
	margin-left:0cm;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:黑体;
	mso-hansi-font-family:宋体;
	mso-bidi-font-family:"Times New Roman";
	color:red;}
 /* Page Definitions */
@page
	{mso-page-border-surround-header:no;
	mso-page-border-surround-footer:no;}
@page Section1
	{size:595.3pt 841.9pt;
	margin:72.0pt 90.0pt 72.0pt 90.0pt;
	mso-header-margin:42.55pt;
	mso-footer-margin:49.6pt;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
 /* List Definitions */
@list l0
	{mso-list-id:69550034;
	mso-list-type:hybrid;
	mso-list-template-ids:1234749500 1199753678 -2076648146 -655973354 1853234084 -542971980 1782372972 248400232 -1480285636 1830333072;}
@list l0:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l1
	{mso-list-id:316422062;
	mso-list-type:hybrid;
	mso-list-template-ids:-1225596234 624046382 276471646 1686175288 1865570400 -540356728 484750830 -529240290 1648256140 -805533860;}
@list l1:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l2
	{mso-list-id:467474736;
	mso-list-type:hybrid;
	mso-list-template-ids:-64087440 -1728135222 942813088 -1927540194 2133756898 -467489732 -149668906 -105344050 -720879468 -7824894;}
@list l2:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l3
	{mso-list-id:595482447;
	mso-list-type:hybrid;
	mso-list-template-ids:1360704102 1993908048 1519527296 309769260 -2100001268 -201007714 -1559451290 1260127766 -132479704 -1212398768;}
@list l3:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l4
	{mso-list-id:1373531625;
	mso-list-type:hybrid;
	mso-list-template-ids:-1665468952 -1969192192 776085438 1013115082 481885586 1580109162 -2012573406 1381299482 2144867070 206760116;}
@list l4:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l5
	{mso-list-id:1971278398;
	mso-list-type:hybrid;
	mso-list-template-ids:-1341064736 -1985983742 539638094 -971965616 -516283074 397814442 417234892 597228920 -1325650984 1382696744;}
@list l5:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
@list l5:level2
	{mso-level-number-format:bullet;
	mso-level-text:o;
	mso-level-tab-stop:72.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:"Courier New";
	mso-bidi-font-family:"Times New Roman";}
@list l6
	{mso-list-id:1971595594;
	mso-list-type:hybrid;
	mso-list-template-ids:-2120820128 229902220 -255423420 2098610618 -24626422 2024675744 -1812543848 1673150696 1491757316 1391621122;}
@list l6:level1
	{mso-level-number-format:bullet;
	mso-level-text:\F0B7;
	mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;
	mso-ansi-font-size:10.0pt;
	font-family:Symbol;}
ol
	{margin-bottom:0cm;}
ul
	{margin-bottom:0cm;}
-->
</style>
</head>

<body lang=ZH-CN style='tab-interval:21.0pt'>

<div class=Section1>

<p class=style1 align=center style='text-align:center'>第三章 习题解答</p>

<p class=style1><span lang=EN-US style='font-family:宋体;mso-ascii-font-family:
黑体;mso-fareast-font-family:黑体'>&nbsp;</span><span lang=EN-US>http://202.117.80.9/jp2004/05/kcwz/stk/khxt/a4.htm</span></p>

<p><span lang=EN-US>1．从略</span></p>

<p><span lang=EN-US>2．</span></p>

<p><span lang=EN-US><img width=519 height=181 id="_x0000_i1025"
src="编译原理-课后习题.files\a03-01.jpg"></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p><span lang=EN-US>3 假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河</span></p>

<p>用到的状态<span lang=EN-US>1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸 4:狐狸和山羊在右岸5:狐狸和白菜在右岸 6:山羊和白菜在右岸F:全在右岸</span></p>

<p><span lang=EN-US><img width=408 height=198 id="_x0000_i1026"
src="编译原理-课后习题.files\a03-02.jpg"></span></p>

<p><span lang=EN-US>4 证明：只须证明文法G:A→αB 或A→α （A,B∈VN, α∈VT+）</span></p>

<p>等价于<span lang=EN-US>G1:A→aB 或A→a (a∈VT+)</span></p>

<ul type=disc>
 <li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
     mso-list:l3 level1 lfo1;tab-stops:list 36.0pt'><span lang=EN-US>G1的产生式中
     A→aB, 则B也有B→bC ,C→cD …. </span></li>
</ul>

<p>所以有<span lang=EN-US> A →abc…B’,a,b,c…∈VT,B’∈VN</span></p>

<p>所以与<span lang=EN-US>G等价。</span></p>

<p><span lang=EN-US>2）G的产生式A→αB，α∈VT+，因为α是字符串，所以肯定存在着一个终结符a， 使A→aB</span></p>

<p>可见两者等价，所以由此文法产生的语言是正规语言。</p>

<p><span lang=EN-US>5 </span></p>

<p><span lang=EN-US>6 根据文法知其产生的语言是</span></p>

<p><span lang=EN-US>L={ambnci| m,n,i≧1}</span></p>

<p>可以构造如下的文法<span lang=EN-US>VN={S,A,B,C}, VT={a,b,c}</span></p>

<p><span lang=EN-US>P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c}</span></p>

<p>其状态转换图如下<span lang=EN-US>:</span></p>

<p><span lang=EN-US><img width=352 height=117 id="_x0000_i1027"
src="编译原理-课后习题.files\a03-03.jpg"></span></p>

<p><span lang=EN-US>7 (1) 其对应的右线性文法是:</span></p>

<p><span lang=EN-US>A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B</span></p>

<p><span lang=EN-US>(2) 最短输入串011</span></p>

<p><span lang=EN-US>(3) 任意接受的四个串</span></p>

<p><span lang=EN-US>011,0110,0011,000011</span></p>

<p><span lang=EN-US>(4) 任意以1打头的串.</span></p>

<p><span lang=EN-US>8 从略。</span></p>

<p><span lang=EN-US>9</span></p>

<p><span lang=EN-US><img width=390 height=359 id="_x0000_i1028"
src="编译原理-课后习题.files\a03-04.jpg"></span></p>

<p><span lang=EN-US><img width=384 height=515 id="_x0000_i1029"
src="编译原理-课后习题.files\a03-05.jpg"></span></p>

<p>（<span lang=EN-US>2）相应的3型文法</span></p>

<p><span lang=EN-US>(i) S →aAS→bS A→aA A→bB B→a|aB B→b|bB</span></p>

<p><span lang=EN-US>(ii) S→aA|a S→bB B→aB | bB A→aB A→b|bA</span></p>

<p><span lang=EN-US>(iii) S→aA S→bB A→bA A→aC B→aB B→bC C→a|aC C→b|bC</span></p>

<p><span lang=EN-US>(iv) S→bS S→aA A→aC A→bB B→aB B→bC C→a|aC C→b|bC</span></p>

<p>（<span lang=EN-US>3）用自然语言描述输入串的特征</span></p>

<p><span lang=EN-US>(i) 以任意个(包括0)b开头，中间有任意个（大于1）a，跟一个b,还可以有一个由a,b组成的任意字符串</span></p>

<p><span lang=EN-US>(ii) 以a打头，后跟任意个（包括0）b</span></p>

<p><span lang=EN-US>(iii)以a打头，中间有任意个（包括0）b,再跟a,最后由一个a,b所组成的任意串结尾或者</span></p>

<p>以<span lang=EN-US>b打头，中间有任意个（包括0）a,再跟b,最后由一个a,b所组成的任意串结尾</span></p>

<p><span lang=EN-US>(iv)以任意个（包括0）b开头,中间跟aa最后由一个a,b所组成的任意串结尾或者</span></p>

<p>以任意个（包括<span lang=EN-US>0）b开头，中间跟ab后再接任意（包括0）a再接b，最后由一个a,b所组成的任意串结尾</span></p>

<p><span lang=EN-US>10 （1）G1的状态转换图：</span></p>

<p><span lang=EN-US><img width=465 height=243 id="_x0000_i1030"
src="编译原理-课后习题.files\a03-06.jpg"></span></p>

<p><span lang=EN-US>G2的状态转换图：</span></p>

<p><span lang=EN-US><img width=514 height=196 id="_x0000_i1031"
src="编译原理-课后习题.files\a03-07.jpg"></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p><span lang=EN-US>(2) G1等价的左线性文法：</span></p>

<p><span lang=EN-US>S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→a</span></p>

<p><span lang=EN-US>G2等价的右线性文法：</span></p>

<p><span lang=EN-US>S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a</span></p>

<p>（<span lang=EN-US>3）对G1文法,abb的推导序列是：</span></p>

<p><span lang=EN-US>S=&gt;aA=&gt;abB=&gt;abb</span></p>

<p>对<span lang=EN-US>G1’文法，abb的推导序列是：</span></p>

<p><span lang=EN-US>S=&gt;Bb=&gt;Abb=&gt;abb</span></p>

<p>对<span lang=EN-US>G2文法，aabca的推导序列是：</span></p>

<p><span lang=EN-US>S=&gt;Aa=&gt;Cca=&gt;Babca=&gt;aabca</span></p>

<p>对<span lang=EN-US>G2’文法，aabca的推导序列是：</span></p>

<p><span lang=EN-US>S=&gt;aB=&gt;aabC=&gt;aabcA=&gt;aabca</span></p>

<p>（<span lang=EN-US>4）对串acbd来说，G1,G1’文法都不能产生。</span></p>

<p><span lang=EN-US>11将右线性文法化为左线性文法的算法：</span></p>

<ul type=disc>
 <ul type=circle>
  <li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
      auto;mso-list:l5 level2 lfo2;tab-stops:list 72.0pt'>（<span lang=EN-US>1）对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则若A不是开始符，B→Aa;
      </span></li>
  <li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
      auto;mso-list:l5 level2 lfo2;tab-stops:list 72.0pt'>（<span lang=EN-US>2）对于G中每一个形如A→a的产生式,将其变为S→Aa
      </span></li>
 </ul>
</ul>

<p><span lang=EN-US>12 (1)</span></p>
12

⌨️ 快捷键说明

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