上下文无关文法

1、上下文无关文法又称CFG。许多CFG由几个较简单的CFG合并起来。可以先构造每个部分的CFG，比如：S1,S2,S3.......,Sk。然后加入新的规则S->S1|S2|....|Sk

2、例如：构造语言{0^n 1^n|n>=0}∪{1^n0^n|n>=0}的CFG，

1）构造{0^n 1^n|n>=0}

S1->0　S1 1|ε

2){1^n 0^n|n>=0}

S2->1 S2 0|ε

3)整合

S->S1|S2

3、如果语言是正则的，可以构造它的DFA，再由DFA转换成CFG。转换方法如下：

1)对于DFA的每个状态Qi,设一个变元Ri。如果δ(Qi,a)=Qj是DFA中的一个转移，则把规则Ri->aRj加入到CFG中。

2）如果Qi是DFA的接受（终止）状态，则把规则Ri->ε加入到DFG中。

3)设Q0为DFA的起始状态，R0为CFG的起始变元。

4、如果CFG中的字符串，有两个相对应的子串，则可使用R->uRv之类的，u对应于v

5、如果字符串有种结构，该结构递归地作为另一种结构的一部分出现，则将生成这种结构的变元放在规则中对应的可能递归出现这种结构的地方。

上下文无关文法是一个4元组(V,∑,R,S),其中:

1)V是一个有穷集合,称为变元集

2)∑是一个与V不相交的有穷集合,称为终结符集

3)R是一个有穷的规则集,每一条规则由一个变元、一个箭头、一个由变元和终结符组成的字符串。

4)S∈V是起始变元。

如G=({S},{a,b},R,S)，其中R为

S->aSb|SS|ε

该文法产生abab,aaabbb,aababb等字符串。