3型文法,又称正规文法,其本质与有限状态自动机相关。正规文法有几种等价的定义,其中一种是通过左线性文法来理解。左线性文法规定,产生式的左部仅包含一个非终结符号,右部则必须为空串、一个终结符号,或是非终结符号后面跟着一个终结符号。例如,规则A->a, A->aB, B->a, B->cB,符合3型文法的要求,因为A的产生式保持了这种结构。
然而,一些推导方式并不符合3型文法的定义。例如,A->ab, A->aB, B->a, B->cB中,A->ab的结构不符合左线性或右线性文法,因为它直接连接了两个终结符。正确的形式应该是A->aB,这样才符合3型文法对产生式的限制。另一个例子是A->a, A->Ba, B->a, B->cB,这里B->cB应改为B->Bc,因为正规文法不能同时满足右线性规则A→α|αB和左线性规则A→α|Bα,只能选择其中一种规则来定义。
在这些规则中,大写字母代表非终结符,小写字母则代表终结符,这是3型文法定义中的关键标识。理解这些规则对于正确构造和解释正规文法至关重要。
形式文法,计算机科学中的概念,在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。形式文法描述形式语言的基本想法是,从一个特殊的初始符号出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。