一、右线性文法
定义：（右线性文法）一个文法 G=(V, T, P, S) 如果只包含如下模式的产生式
A-> xB
A-> x
其中 A, B in V, x in T*，则称 G 是右线性的。右线性文法产生的语言称为右线性语言。
二、右线性语言与正则语言的等价性
定理：给定一个右线性文法 G，则存在一个 nfa A，使得 L(G)=L(A).
可以把 nfa A 具体地构造出来。比如 V_i-> xV_j，则添加两个状态 V_i, V_j, 并在 V_i, V_j 间添加若干``匿名''状态（名字可以随机选取，只要不冲突）使得从状态 V_i 通过 x 能到达 V_j, 而通过 x 的任何前缀就会死掉。另给定一个状态 V_f 作为唯一的终止状态，对产生式 V_k -> x, 在状态 V_k 和 V_f 间添加若干``匿名''状态，使得通过 x 可以从状态 V_k 到达 V_f.
定理：给定一个正则语言 R, 则存在一个右线性文法 G，使得 L(G)=R.
设 R 对应的 dfa 为 A, 转移函数为 f. 设 S_i, S_j 是 A 的两个状态，并且 f(S_i, a) = S_j。这个状态转移可以用 S_i->aS_j 来刻画。若 S_k 为接受状态，则可以用 S_k->e 来刻画。
三、正则文法与正则语言
从上面的两个定理可以知道，右线性文法与 dfa 是等价的。类似地，我们有左线性文法，它与 dfa 也是等价的。所以左、右线性文法是等价的。
定义：（正则文法）左线性文法等价于右线性文法，它们统称为正则文法。
定理：正则文法与 dfa 等价。