設有兩文法G1和G2，如果L（G1）=L（G2），則稱G1和G2為等價文法。
概念,定理,
概念
設有兩文法G1和G2，如果L（G1）=L（G2），則稱G1和G2為等價文法。
定理
例： G1[Z]: Z→abZA|a
A→b
經過等價變換後可得到文法G2[Z']:
G2[Z']: Z' →Z
Z →abZA|a
A →b
對任一文法G1均可構造文法G2，使得L(G1）=L(G2），並且G2中的每個非終極符出現於某句型中.
步驟：
⒈初始化β={ Z },Z為文法G1的初始符；
⒉遞歸擴充β：
β=β∪{ D| A→xDy∈G1,A∈β，D∈Vn };
⒊從G1中刪去左部不在β中的那些產生式.
例： G1[Z]: Z→abZA|a
A→b
B→ab
解： 按照算法，這個等價變換可分為三步：
⑴.初始化β={ Z }
⑵.遞歸擴充β={ Z,A }
⑶.刪去無用的產生式 B→ab可得：
G2[Z]: Z→abZA|a
A→b
對任一文法G1均可構造文法G2，使得L(G1）=L(G2），並且在G2中沒有形如A→B的產生式，其中B∈Vn.
☆ 特型產生式： 形如A→B 的產生式，其中 B∈Vn.
步驟：
⒈對每一個A∈Vn，求：
βA={ F| AF,F∈Vn };
⒉令G1中所有非特型產生式為G2的產生式；
⒊若有F∈βA，且有 F→x 是非特型產生式，則令 A→x ∈G2;
⒋刪去無用的產生式.
例：G1[A]:A→B|dD
B→A|E|b
E→B|e
D→d|Da
解： ⑴.求得：
βA={ B,A,E }
βB={ A,B,E }
βD={ }
βE={ B,A,E }
⑵.先令G1中的非特型產生式為G2的產生式：
A→dD
B→b
E→e
D→d|Da
⑶.再擴充下列產生式：
A→dD|b|e
B→dD|b|e
E→dD|b|e
此時G2[A]:
A→dD|b|e
B→dD|b|e
E→dD|b|e
D→d|Da
⑷.刪去無用的產生式：（根據定理二）
.初始化β={ A }
.擴充β={ A,D }
.故刪去 B→dD|b|e 和 E→dD|b|e
最後得到 G2[A]:
A→dD|b|e
D→d|Da
對任一文法G1(G1不能識別空串ε）均可構造文法G2，使得L(G1）=L(G2），並且G2中沒有ε產生式.
步驟：
⒈初始化β={ A|A→ε∈G1};
⒉遞歸擴充β=β∪{ D|D→x∈G1,x∈β的正閉包};
⒊從G1中刪去所有產生式；
⒋從G1中刪去只能導出空串的非終極符（即對於非終極符A只有A→ε一個產生式）；
⒌若有產生式 A→C1C2...Cn，且Ci∈β（1≤i≤n），則擴充添加產生式
A→C1...C(i-1）C(i+1）...Cn,
重複此過程，直到不出現新產生式為止.
例： 文法G1[A]:
A→aBbD
D→BB
B→b|ε
解： .初始化β={ B }
.遞歸擴充β={ B,D }
.刪去ε產生式B→ε
.無只能導出空串的非終極符
.重複擴充添加產生式：
A→aBb
A→abD
A→ab
D→B
故等價文法G2[A]:
A→aBbD|aBb|abD|ab
D→BB|B
B→b
五. 對於任一文法G1均可構造文法G2，使得L(G1）=L(G2），並且G2沒有直接左遞歸的產生式.
步驟：
⒈對於文法A→Aβ|γ（其中β非空，γ不以A開頭），可改寫成：
A→γA'
A'→βA'|ε
（即將直接左遞歸變換成直接右遞歸）
⒉同理，對於產生式A→Aβ1|Aβ2|...|Aβn|γ1|γ2|...|γm
（其中βi 非空，1≤i≤n，γj 不以A開頭，1≤j≤m），可改寫成：
A→γ1A'|γ2A'|...|γmA'
A'→β1A'|β2A'|...|βnA'|ε
例： 文法G1[E]:
E →E+T |T
T → T*F |F
F → i | (E)
經過等價變換後，得到文法G2[E]:
E → TE'
E' → +TE'|ε
T →FT'
T' →*FT'|ε
F → i| (E)
