第一章 引论

（形式语言的内容）

第一节  例子语言

一.字母表：任意字符的集合。

   语言：字母表的某些字符串的集合。

  自然语言的描述方式：（规则）

   1.（）是合法的该语言的最基本的串；

   2.若S是一个合法的串，则（S）是合法的串。

   3.若S是一个合法的串，则SS是合法的串。

  根据这些形成规则，可以：

（1）产生任意合法的该集合的串；

  (2)   判断产生的串是不是合法的。

 产生串的过程串为：从S开始，反复利用产生式的右边代替产生式的左边（称之为推导过程），最后，可以得到匹配的（）组成的串。

虽然产生式的个数是有限的，但是规则是递归的，因而，所有的小括号匹配的串（有无限个）均可以由它们产生，它们组成的集合就称为一个语言。

S称为非终结符，是可以被替换的。