第 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：