首页 > 代码库 > [龙书]理论练习题(二)

[龙书]理论练习题(二)

不对之处,敬请指出!


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∑ - {", /, \*}

CommQuote| NonStarQuote|Star+(NonStarSlashQuote|Quote)

L/StarComm*Star+/


3、有文法G:SaSb| bSa | abS | baS | Sab | Sba | ε

1)证明文法G是二义性文法

证:对于ab可以给出如下两棵不同的语法分析树


故本文法二义。


(2)文法G识别的语言是什么?

定义于字母表{a,b}之上的,a和b数目相等的符号串。


(3)将文法G改写成无二义性的文法G‘,使得L(G)=L(G‘)  (难度过高,不作要求)

SaBS| bAS |ε

AbAA| a

B aBB| b





[龙书]理论练习题(二)