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

作者：顾恒一阶语言乔姆斯基层级生成文法形式文法正则语言

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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社