文法类型： 0型文法：对于推导式α→β,那么α∈(Vn∪Vt)*且至少含有一个非终结符，β∈(Vn∪Vt)*，则该推导式属于~。 1型文法：也叫上下文有关文法，此文法对应线性有界自动机。1型文法在0型文法的基础上满足|β|>=|α|,则该推导式属于~。||代表长度。 2型文法：也叫上下文无关文法，它对应下推自动机。2型文法在1型文法的基础上满足推导式(α→β)的左侧都是非终结符。 3型文法：也叫正规文法，它对应有限状态自动机。它在2型文法的基础上满足A→a|aB(一个非终结符推导出一个终结符或一个终结符带一个非终结符。右线性)，A→a|Ba(左线性)。 |代表“或”的意思。

评论