通常的逻辑学教材都会讲到一阶语言是一种形式语言,但是所讲的形成规则一般都是规定什么是公式,而非如何构造公式.而本文从乔姆斯基的形式文法的观点重新理解一阶语言的形成过程.首先由于一阶语言是递归的,因此它一定是递归可枚举语言,从而存在一套形式文法生成它.本文就找到了一套可以生成一阶语言的形式文法,而且这套文法是上下文无关的,因此一阶语言不止是递归可枚举语言,还是上下文无关语言.更进一步地,借助哥德尔编码还可以构造一套生成一阶语言的正则文法,从而可以得出更强的结论:一阶语言是正则语言.
一阶语言 乔姆斯基层级 生成文法 形式文法 正则语言