- 1、本文档共13页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第2章 习题解答
1.文法G[S]为:
S-Ac|aB
A-ab
B-bc
写出L(G[S])的全部元素。
[答案]
S=Ac=abc
或S=aB=abc
所以L(G[S])={abc}
==============================================
2. 文法G[N]为:
N-D|ND
D-0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么?
[答案]
G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}
N=ND=NDD.... =NDDDD...D=D......D
===============================================
3.已知文法G[S]:
S→dAB? A→aA|a? B→ε|bB
问:相应的正规式是什么?G[S]能否改写成为等价的正规文法?
[答案]
正规式是daa*b*;
相应的正规文法为(由自动机化简来):
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε
===============================================================================
4.已知文法G[Z]:
Z-aZb|ab
写出L(G[Z])的全部元素。
[答案]
Z=aZb=aaZbb=aaa..Z...bbb= aaa..ab...bbb
L(G[Z])={anbn|n=1}
==============================================================================
5.给出语言{anbncm|n=1,m=0}的上下文无关文法。
[分析]
本题难度不大,主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A-β,A∈Vn,β∈(Vn∪Vt)*,注意关键问题是保证anbn的成立,即“a与b的个数要相等”,为此,可以用一条形如A-aAb|ab的产生式即可解决。
[答案]
构造上下文无关文法如下:
S-AB|A
A-aAb|ab
B-Bc|c
[扩展]
凡是诸如此类的题都应按此思路进行,本题可做为一个基本代表。基本思路是这样的:
要求符合anbncm,因为a与b要求个数相等,所以把它们应看作一个整体单元进行,而cm做为另一个单位,初步产生式就应写为S-AB,其中A推出anbn,B推出cm。因为m可为0,故上式进一步改写为S-AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题,都应写为A-aAb|ab形式,对于B就很容易写成B-Bc|c了。
==============================================================================
6 .写一文法,使其语言是偶正整数集合。
要求:
(1)允许0开头;
(2)不允许0开头。
[答案]
(1)允许0开头的偶正整数集合的文法
E-NT|G|SFM
T-NT|G
N-D|1|3|5|7|9
D-0|G
G-2|4|6|8
S-NS|ε
F-1|3|5|7|9|G
M-M0|0
(2)不允许0开头的偶正整数集合的文法
E-NT|D
T-FT|G
N-D|1|3|5|7|9
D-2|4|6|8
F-N|0
G-D|0
=============================================================================
7.已知文法G:
E-E+T|E-T|T
T-T*F|T/F|F
F-(E)|i
试给出下述表达式的推导及语法树
(1)i;? (2)i*i+i ??(3)i+i*i ?(4)i+(i+i)
[答案]
(1)E=T=F=i
(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i
(3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i
(4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T) =i+(i+T)=i+(i+F)=i+(i+i)
8 .为句子i+i*i构造两棵语法树,从而证明下述文法G[表达式]是二义的。
〈表达式〉-〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i
〈运算符〉-+|-|*|/
[答案]
可为句子i+i*i构造两个不同的最
文档评论(0)