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