一、右線性文法
定義：（右線性文法）一個文法 G=(V, T, P, S) 如果只包含如下模式的產(chǎn)生式
A-> xB
A-> x
其中 A, B in V, x in T*，則稱 G 是右線性的。右線性文法產(chǎn)生的語言稱為右線性語言。
二、右線性語言與正則語言的等價性
定理：給定一個右線性文法 G，則存在一個 nfa A，使得 L(G)=L(A).
可以把 nfa A 具體地構造出來。比如 V_i-> xV_j，則添加兩個狀態(tài) V_i, V_j, 并在 V_i, V_j 間添加若干``匿名''狀態(tài)（名字可以隨機選取，只要不沖突）使得從狀態(tài) V_i 通過 x 能到達 V_j, 而通過 x 的任何前綴就會死掉。另給定一個狀態(tài) V_f 作為唯一的終止狀態(tài)，對產(chǎn)生式 V_k -> x, 在狀態(tài) V_k 和 V_f 間添加若干``匿名''狀態(tài)，使得通過 x 可以從狀態(tài) V_k 到達 V_f.
定理：給定一個正則語言 R, 則存在一個右線性文法 G，使得 L(G)=R.
設 R 對應的 dfa 為 A, 轉(zhuǎn)移函數(shù)為 f. 設 S_i, S_j 是 A 的兩個狀態(tài)，并且 f(S_i, a) = S_j。這個狀態(tài)轉(zhuǎn)移可以用 S_i->aS_j 來刻畫。若 S_k 為接受狀態(tài)，則可以用 S_k->e 來刻畫。
三、正則文法與正則語言
從上面的兩個定理可以知道，右線性文法與 dfa 是等價的。類似地，我們有左線性文法，它與 dfa 也是等價的。所以左、右線性文法是等價的。
定義：（正則文法）左線性文法等價于右線性文法，它們統(tǒng)稱為正則文法。
定理：正則文法與 dfa 等價。