上下文无关文法(CFG, Context-Free Grammar)
CFG为一个四元组:
G=(V,T,P,S)
- V:非终结符(变量、语法范畴)的有穷集
- T:终结符的有穷集
- 终结符和非终结符不能有重复V∩T=∅
- P:产生式的有穷集,产生式可以表示为A→α,读作“A定义为α”,其中
- A:产生式的头/左部,A∈V
- →:产生式符号,表示“定义为”
- α:产生式的体/右部,α∈(V∪T)∗是一个字符串
- S:初始符号,S∈V
注:
- 多条产生式A→α1,A→α2,A→α3,…合写为A→α1∣α2∣α3∣…
- 变元A的全体产生式称为A产生式
规约(由字符串到CFG)和派生(由CFG到字符串)
对于一个CFGG=(V,T,P,S),字符串α,β,γ∈(V∪T)∗
“可派生”和“可规约”符号G⇒定义
用A→γ的右部替换αAβ中的变元A得到αγβ
αAβG⇒αγβ:=αAβ可派生出αγβαγβ可规约为αAβ:=(∃A∈V)A→γ∈P
“m步派生”符号G⇒m定义
α经过m次派生过程可以得到β
αG⇒mβ:=(∃α1,…αm∈(V∪T)∗,αiG⇒αi+1)α=α1,β=αm
“多步派生”符号G⇒∗定义
α经过多次派生过程可以得到β
αG⇒∗β:=(∃m∈N+)αG⇒mβ
若语境中G已知,则G可省略。G⇒、G⇒m、G⇒∗可分别省略为⇒、⇒m、⇒∗。
“最左派生”符号lm⇒定义
只替换字符串最左边的变元
αAβlm⇒αγβ:=αAβ⇒αγβ∧α中没有变元
同理可定义“m步最左派生”lm⇒m和“多步最左派生”lm⇒∗。
“最右派生”符号rm⇒定义
只替换字符串最右边的变元
αAβlm⇒αγβ:=αAβ⇒αγβ∧β中没有变元
同理可定义“m步最右派生”rm⇒m和“多步最右派生”rm⇒∗。
任何派生都有等价的最左和最右派生过程
A⇒∗w⇔Alm⇒∗w⇔Arm⇒∗w
案例:回文语言L={w∈{0,1}∗∣w=wR}的CFG
G=({A},{0,1},{A→ε∣0∣1∣0A0∣1A1},A)
例如,一个回文串派生过程A⇒70101001001010可以表示如下:
001010010101010010100010100A⇓使用产生式A→0A0A0⇓使用产生式A→1A1A10⇓使用产生式A→0A0A010⇓使用产生式A→1A1A1010⇓使用产生式A→0A0A01010⇓使用产生式A→0A0A001010⇓使用产生式A→11001010
上下文无关语言(CFL, Context-Free Language):上下文无关文法的语言
CFGG=(V,T,P,S)的语言定义为:由初始符号派生的所有仅由终结符构成字符串的集合
L(G)={w∣w∈T∗,SG⇒∗w}
在上下文无关文法派生的每一步αAβG⇒αγβ,γ都只与A有关而与α和β无关,因此称为“上下文无关”语言。
α是G的句型α是G的左句型α是G的右句型α是G的句子:=:=:=:=α∈(V∪T)∗∧S⇒∗αα∈(V∪T)∗∧Slm⇒∗αα∈(V∪T)∗∧Srm⇒∗αα∈T∗∧S⇒∗α
以下3个案例来自于《正则语言》一节,它们都不是正则语言,但是是上下文无关语言。
上下文无关语言的封闭性
代换
代换是一个字母表Σ上的字符串到另一个字母表Γ上的语言Γ∗的函数s:Σ∗→2Γ∗。递归定义:
s(ε)s(a)s(xa)s(L)={ε}=La=s(x)s(a)=x∈L⋃s(x)(a∈Σ,La∈2Γ∗)(x∈Σ∗)空串的代换字符的代换字符串的代换语言的代换
代换的封闭性(未完成)
对于字母表Σ上的一个CFLL∈Σ∗,那么对于代换s有如下定理:
(∀a∈Σ)s(a)是CFL⇒s(L)是CFL
证明:
设:
- CFLL的CFG是G=(V,T,P,S),即L=L(G);
- s(a)的CFG是Ga=(Va,Ta,Pa,Sa),即s(a)=L(Ga)。
那么构造一个CFGG′:
G′=(V′,T′,P′,S)
其中:
- V′=V∪(⋃a∈TVa),变元是原CFL和所有代换CFL的变元并集
- T′=⋃a∈TTa,终结符中只包含代换CFL的终结符,不包含原CFL的终结符
- P′中包含⋃a∈TPa和P,但要将P中产生式的每个终结符a替换为对应的代换文法Ga的开始符号Sa。
案例
案例:语言L=∑n=0∞0n1n={0n1n∣n≥0}的CFG
G=({S},{0,1},{S→ε∣0S1},S)
案例:语言L={w∣w由数量相等的01构成}的CFG
G=({S},{0,1},{S→ε∣S0S1S∣S1S0S},S)
案例:语言L={0i1j∣i>j}的CFG
G=({S,A,B},{0,1},{S→AB,A→A0∣0,B→ε∣0B1},S)
经典案例:四则运算表达式的CFG
表示一个由加减乘除和括号以及二进制数表示的四则运算CFG
G={{E,I},{0,1,+,−,×,÷,(,)},P,E}
其中,产生式的有穷集P为:
P=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧EEEI→E+E∣E−E→E×E∣E÷E→(E)∣I→0∣1∣I0∣I1⎭⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎫
如果一个上下文无关文法G=(V,T,P,S)的每一个产生式都具有如下形式:
AA→BC→a(A,B,C∈V∧B,C=S)(A∈V∧a∈T)
那么称此上下文无关文法为乔姆斯基范式。
可以证明任何上下文无关文法都可以转化为乔姆斯基范式,其证明过程也是将任意上下文无关文法转化为乔姆斯基范式的方法,比较简单,此处略。
乔姆斯基范式的性质
- 派生出长度为n的串恰好需要2n−1步
- 其中n−1步产生一个由变元组成的长度为n的串
- 其中n步将长度为n的变元串派生为终结符串
- 存在多项式时间算法判断任意字符串是否在给定的乔姆斯基范式
如果一个上下文无关文法G=(V,T,P,S)不含空串ε∈T,且每一个产生式都具有如下形式:
A→aα(a∈T∧α∈(V∪T∪{ε})∗)
那么称此上下文无关文法为格雷巴赫范式。
可以证明任何不含空串ε∈T的上下文无关文法都可以转化为格雷巴赫范式,其证明过程也是将任意上下文无关文法转化为格雷巴赫范式的方法,比较简单,此处略。
乔姆斯基范式的性质
- 派生出长度为n的串恰好需要n步
- 每个产生式引入一个终结符
上下文无关语言的泵引理
非上下文无关语言
“上下文有关语言”