首页 > 代码库 > [龙书]理论练习题(二)
[龙书]理论练习题(二)
不对之处,敬请指出!
3.3.3:试说明在一个长度为n的字符串中,分别有多少个
3.3.5:写出以下语言的正规式定义
(1)顺序包含所有5个元音字母的小写字符串。
NonVowel → [b-df-hj-np-tv-z]
L→(NonVowel| a)*a(NonVowel|e)*e(NonVowel|i)*i(NonVowel|o)*o(NonVowel|u)*uNonVowel*
(2)所有字母按升序排列的小写字母串
a*b*c*...y*z*
(3)注释,即/*和*/之间的串,且串中没有不在双引号(")中的*/
NonQuote→∑ - {"}
Quote→"NonQuote*"
Star→\*
NonStarQuote∑ - {", \*}
NonStarSlashQuote→∑ - {", /, \*}
Comm→Quote| NonStarQuote|Star+(NonStarSlashQuote|Quote)
L→/StarComm*Star+/
3、有文法G:S→aSb| bSa | abS | baS | Sab | Sba | ε
1)证明文法G是二义性文法
证:对于ab可以给出如下两棵不同的语法分析树
故本文法二义。
(2)文法G识别的语言是什么?
定义于字母表{a,b}之上的,a和b数目相等的符号串。
(3)将文法G改写成无二义性的文法G‘,使得L(G)=L(G‘) (难度过高,不作要求)
S→aBS| bAS |ε
A→bAA| a
B →aBB| b
[龙书]理论练习题(二)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。