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