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

不对之处，敬请指出！3.3.3:试说明在一个长度为n的字符串中，分别有多少个3.3.5:写出以下语言的正规式定义（１）顺序包 不对之处，敬请指出！

3.3.3:试说明在一个长度为n的字符串中，分别有多少个

3.3.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

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