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

摘要：

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

关键词：一阶语言、乔姆斯基层级、生成文法、形式文法、正则语言

所属期刊栏目：31

分类号：O141(数理逻辑、数学基础)

资助基金：重庆市重点文科基地重点项目"动态认知逻辑的拓展研究"成果之一,项目11SKB16

在线出版日期：2013-08-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：13-20