形式语言理论

　　形式语言理论（汉语拼音：Xingshi Yuyan Lilun；英语：Formal Language Theory），用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的产生方式、一般性质和规则的理论。形式语言是模拟这些语言的一类数学语言，它采用数学符号，按照严格的语法规则构成。从广义上说，形式语言是符号取自某个字母表的字符串的集合。

　　如同自然语言具有语法规则一样，形式语言也是由形式文法生成的。一个形式文法是一个有穷变元集合，这些变元也称为非终结符或语法范畴。每个变元都可以用来定义语言，定义方式可以是递归的，即通过一些称为终结符的原始符号，加上变元自身，递归地加以定义。和变元有关的规则称为生成式，生成式决定了语言是如何构造出来的。一个典型的生成式表示：给定变元所代表的语言包含这样一些字符串，它们是通过连结运算，将另外某些变元语言中的字符串和若干终结符连结起来而得到的。

　　形式文法被严格地定义为四元组G＝（V，T，P，S），其中V和T分别是变元和终结符的有穷集合，并且V和T分别是变元和终结符的有穷集合，并且V和T没有公共元素，即V∩T=Æ。S是一个特殊变元，称为开始符号。P是生成式的有穷集合，生成式的基本形式是：a→β，这里a和β，这里a和β都是（V∪T）*中的元素，即它们都是由变元和终结符组成的符号串，但要求a至少含有一个非终结符。在形式文法定义中，生成式集合P是至关重要的 。 在对使用符号的惯例作某些约定后，仅仅考查生成式，就能推断出一个文法的变元、终结符和开始符号，故可以友爱过列出生成式来定义一个形式文法。

　　同形式文法G＝（V，T，P，S）产生的形式语言记为L（G）。L（G）中的字符串ω都具有如下特点：①该字符串仅由终结符组成，即ω∈T*；②该字符串能由开始符号S派生出来，即从S出发，通过应用零个或多个P中的生成式，由S可以推导出ω。

　　根据P中生成式a→β的特点，可以将形式文法及其产生的形式语言分类，构成所谓的形式语言谱系。形式语言理论中重点研究四类文法和语言：①0型文法。又称为无限制文法。这种文法对生成式a→β不作特殊限制，a和β可以是任意的文法符号串，当然a不能是空字符串。0型文法是形式语言谱系中最大的文法类。由0型文法产生的形式语言恰是图灵机所识别的语言类，即递归可枚举语言。②1型文法。又称为上下文有关文法。这种文法要求生成式a→β满足｜a｜≤｜β｜，即β要至少和a一样长。 由1型文法产生的语言称为1型语言或上下文有关语言。1型语言恰是非确定型线性有界自动机所识别的语言类。③2型文法。又称为上下文无关文法。这种文法要求生成式a→β中的a必须是变元。由2型文法产生的语言称为2型语言或上下文无关语言。2型语言恰是由下推自动机所识别的语言类。④3型文法。又称为正则文法。这种文法分为两种类型：第一类要求生成式的形式必须是A→ωB或A→ω，其中A，B都是变元，ω是终结符串（可以是空串），这种特殊的正则文法称为右线性文法。第二类正则文法称为左线性文法，它要求生成式必须是A→Bω，或A→ω的形式。由正则文法生成的语言称为正则语言，它恰是有穷自动机所识别的语言类。

　　上述定义的4种语言类具有依次包含关系，即对于i＝0，1，2，在不考虑空字符串时，i型语言都真包含i＋1型语言 。