“等价文法”的意思、由来-中文百科全书

词条

等价文法

释义

§ 概述

设有两文法G1和G2，如果L（G1）=L（G2），则称G1和G2为等价文法。

§ 文法等价变换(定理)

一. 对任一文法G1均可构造文法G2,使得L(G1)=L(G2),并且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中的每个非终极符出现于某句型中.

步骤:

1.初始化β={ Z },Z为文法G1的初始符;

2.递归扩充β:

β=β∪{ D| A→xDy∈G1, A∈β,D∈Vn };

3.从G1中删去左部不在β中的那些产生式.

例:　 G1[Z]:　 Z→abZA|a

A→b

B→ab

解:　　　按照算法,这个等价变换可分为三步:

(1).初始化β={ Z }

(2).递归扩充β={ Z,A }

(3).删去无用的产生式 B→ab可得:

G2[Z]: Z→abZA|a

A→b

三. 对任一文法G1均可构造文法G2,使得L(G1)=L(G2),并且在G2中没有形如A→B的产生式,其中B∈Vn.

☆ 特型产生式: 形如 A→B 的产生式,其中 B∈Vn.

步骤:

1.对每一个A∈Vn ,求:

βA={ F| AF,F∈Vn };

2.令G1中所有非特型产生式为G2的产生式;

3.若有F∈βA,且有 F→x 是非特型产生式,则令 A→x ∈G2;

4.删去无用的产生式.

例: G1[A]: A→B|dD

B→A|E|b

E→B|e

D→d|Da

解: (1).求得:

βA={ B,A,E }

βB={ A,B,E }

βD={　 }

βE={ B,A,E }

(2).先令G1中的非特型产生式为G2的产生式:

A→dD

B→b

E→e

D→d|Da

(3).再扩充下列产生式:

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

(4).删去无用的产生式:(根据定理二)

.初始化β={ 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中没有ε产生式.

步骤:

1.初始化β={ A|A→ε∈G1};

2.递归扩充β=β∪{ D|D→x∈G1,x∈β的正闭包};

3.从G1中删去所有产生式;

4.从G1中删去只能导出空串的非终极符(即对于非终极符A只有A→ε一个产生式);

5.若有产生式 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没有直接左递归的产生式.

步骤:

1.对于文法A→Aβ|γ(其中β非空,γ不以A开头),可改写成:

A→γA'

A'→βA'|ε

(即将直接左递归变换成直接右递归)

2.同理,对于产生式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)

随便看

百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。