5.1 形式语言
为了给接下来介绍的重要理论问题奠定基础,开始之前,我们先定义一些非常简单的抽象概念。接下来,我们要介绍一个广泛使用的软件工具及其相关机制,并附上一些应用程序。
基本定义 我们从符号(symbol)这个抽象概念开始,这个概念是我们构建后继内容的基础。在数学上,符号可以是能够相互区分的任一标识。在刚开始时,把符号当成一个字符或者数字元素是非常有帮助的。下面我们阐明基本定义。
定义:一个符号集(或字母表)表示有限个符号的一个集合。
定义:一个字符串表示有限符号集的一个序列。
定义:一种形式语言是字符串的一个集合(有可能是无限大的),这些字符串都是由同一个符号集合的元素构成。
你可能会觉得这些定义中的前两个对你来说非常简单和熟悉,因此没有必要给出它们的定义。但是它们定义的这些概念是非常基本的,有一个清晰且明确的定义十分重要。第三个定义对于你来说可能是全新的,所以你应该着重理解它。这是一个简单的定义,而且从现在开始我们可以将术语“字符串的集合”和“形式语言”互换使用。
例如,十进制数字集就是一个你十分熟悉的符号集:{0,1,2,3,4,5,6,7,8,9}。像2147483648这样一个整数是由上面符号集组成的一个字符串,所以我们可以将形式语言正整数(positive integer)定义成由这个符号集构成的不以0为开头的字符串的集合。
二进制字符串。接下来我们分析一个二进制字符串的集合(由二进制符号集组成的形式语言),它仅仅涉及两个符号。具体这两个符号是什么并不重要,我们可以使用{0,1},但是在本章中我们使用{a,b}来避免与整数的0和1产生混淆。确定一种形式语言的最简单的方式就是枚举它的字符串。这是一种可以精确确定形式语言的方法,但我们通常还会用非形式的描述来描述语言。例如,我们可以用“长度为3的二进制字符串”这样的非形式描述来标识形式语言(字符串的集合):{aaa,aab,aba,abb,baa,bab,bba,bbb}。 ...