从乔姆斯基语言层级看一阶语言

Viewing First-order Language from Chomsky's Hierarchy

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

First-order languages are usually referred as formal languages in usual logic textbooks,but generative rules generally defines formula, rather than shows how to construct formula. In this article we il-lustrate a new understanding of the process of the formation of first-order languages from the point of view of Chomsky formal grammars. As a first-order language is recursive, so it must be a recursively enumerable lan-guage, thus there is a formal grammar to generate it. We illustrates one which is also a context-free grammar,hence any first-order language is more than a recursively enumerable language but also a context-free lan-guage. Furthermore, it is proved that first-order languages can also be generated with regular grammars by making use of the Gōdel encoding. Thus we can make a stronger conclusion that any first-order language is al-so a regular language.