| 语言L是有限字母表Σ上有限长度字符串的集合，这个集合中的每个字符串都是按照一定的规则生成的。下面从产生语言的角度出发，给出文法和语言的形式定义。所谓产生语言，是指制定出有限个规则，借助它们就能产生此语言的全部句子。
|
|
|
|
|
| .字母表Σ和字符：字母表是字符的非空有穷集合，字符是字母表Σ中的一个元素。例如Σ=｛a，b｝，a或b是字符。
|
|
|
| .字符串：Σ中的字符组成的有穷序列。例如a，ab，aba，aaaa都是Σ的字符串。
|
|
|
| .字符串的长度：指字符串中的字符个数。如｜aba｜=3。
|
|
|
|
|
| .连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表Σ的任意字符串S，S·ε=ε·S=S。
|
|
|
| .Σ*：是指包括空串ε在内的Σ上所有字符串的集合。例如，设Σ=｛a，b｝，Σ*=｛ε，a，b，aa，bb，ab，ba，aaa，…｝。
|
|
|
| .字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αn。α0=ε，αn=ααn-1=αn-1α（n>0）。
|
|
|
| .字符串集合的运算：设A，B代表字母表Σ上的两个字符串集合。
|
|
|
 或（合并）：A∪B=｛α｜α∈A或α∈B｝。
|
|
|
 积（连接）：AB=｛αβ｜α∈A且β∈B｝。
|
|
|
 幂：An=A·An-1=An-1：A（n>0），并规A0=｛ε｝。
|
|
|
 正则闭包＋：A+=A1∪A2∪A3∪…∪An∪…。
|
|
|
 闭包*：A*+A0∪A+。显然，Σ*=Σ0∪Σ1∪Σ2∪…∪Σn∪…。
|
|
|
|
|
| 描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为G=（VN，VT，P，S）。其中VT是一个非空有限集，其每个元素称为一个终结符；VN是一个非空有限集，其每个元素称为非终结符。VN∩VT=Φ，即VN和VT不含公共元素。令V=VN∪VT，称V为文法G的词汇表，V中的符号称为文法符号，包括终结符和非终结符。S∈VN，称为开始符号，它至少要在一条产生式中作为左部出现。P是产生式的有限集合，每个产生式形如“α→β”。其中，α称为产生式的左部，α∈V+且α中至少含有一个非终结符；β称为产生式的右部，且β∈V*。若干个产生式α→β1，α→β2，…，α→βn的左部相同时，可简写为α→β1｜β2｜…｜βn，称βi（1≤i≤n）为α的一个候选式。
|
|
|
| （1）文法的分类。乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法G=（VN，VT，P，S）的每个产生式α→β，均有α∈（VN∪VT）*，α至少含有一个非终结符，且β∈（VN∪VT）*，则称G为0型文法。对0型文法的每条产生式分别施加以下限制，则可得以下文法：
|
|
|
| .1型文法：G的任何产生式α→β（S→ε除外）均满足｜α｜≤｜β｜（｜x｜表示x中文法符号的个数）。
|
|
|
| .2型文法：G的任何产生式形如A→β，其中A∈VN，β∈（VN∪VT）*。
|
|
|
| .3型文法：G的任何产生式形如A→a或A→aB（或者A→Ba），其中A，B∈VN，a∈VT。
|
|
|
| 0型文法也称为短语文法，其能力相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法，它意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串。例如，若αAβ→αγβ是1型文法的产生式，α和β不全为空，则非终结符A只有在左边是α，右边是β的上下文中才能替换成γ。2型文法就是上下文无关文法，其非终结符的替换无需考虑上下文。3型文法等价于正规式，因此也被称为正规文法或线性文法。
|
|
|
| 若文法G1与文法G2产生的语言相同，即L（G1）=L（G2），则称这两个文法是等价的。
|
|
|
| （2）句子和语言。设有文法G=（VN，VT，P，S）。
|
|
|
.推导与直接推导：推导就是从文法的开始符号S出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列（展开产生式用 表示），直到产生一个终结符的序列时为止。若有产生式α→β∈P，且γ，δ∈V*，则 称为文法G中的一个直接推导，并称γαδ可直接推导出γβδ。显然，对P中的每一个产生式α→β都有 。若在文法中存在一个直接推导序列，即 ，则称α0可推导出αn，αn是α0的一个推导，并记为 。用记号 表示α0=αn或者。
|
|
|
.直接归约和归约：归约是推导的逆过程。若文法G中有一个直接推导 ，则称β可直接归约成α，或α是β的一个直接归约。若文法G中有一个推导 ，则称δ可归约成γ，或γ是δ的一个归约。
|
|
|
.句型和句子：若文法G的开始符号为S，那么，从开始符号S能推导出的符号串称为文法的一个句型，即α是文法G的一个句型，当且仅当有如下推导 ，α∈V*。若X是文法G的一个句型，且 ，则称X是文法G的一个句子，即仅含终结符的句型是一个句子。
|
|
|
| .语言：从文法G的开始符号出发，能推导出的句子的全体称为文法G产生的语言，记为L（G）。
|
|
|
