第 16 题

给出生成下述语言的三型文法：

(1){an|n >=0 }

(2) { anbm|n,m>=1 }

(3){anbmck|n,m,k>=0 }

答案：

(1) S→aS|ε (2) S→aA A→aA|B B→bB|b (3)

A→aA|B B→bB|C C→cC|ε

第 17 题

习题７和习题 11 中的文法等价吗？

答案：

等价。

第 18 题

解释下列术语和概念：

（１） 字母表

（２） 串、字和句子 （３） 语言、语法和语义

答案：

（１）字母表：是一个非空有穷集合。

（２）串：符号的有穷序列。

字：字母表中的元素。

句子：如果 Z x , x ∈V *T 则称 x 是文法 G 的一个句子。

+

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

附加题

问题 1：

给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0

答案：

R = (01 | 10) ( 01 | 10 )*

问题 2：

已知文法 G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC

答案:

G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同.

问题 3：