龙书理论练习题(二)中的哪些题目是针对高级难度的？

本文共计465个文字，预计阅读时间需要2分钟。

在长为n的字符串中，分别有多少个3.3.3和3.3.5：

3.3.3：在长度为n的字符串中，3.3.3表示连续出现三次的数字3。例如，在字符串333中有1个3.3.3，在字符串3343中有2个3.3.3。

3.3.5：在长度为n的字符串中，3.3.5表示数字3后面紧跟着数字3，再后面是数字5。例如，在字符串335中有1个3.3.5，在字符串3335中有2个3.3.5。

不对之处，敬请指出！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

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