2.正规式到正规文法的转换
字母表上的正规式到正规文法G= (VN,VT,P,S) 的转换方法如下:
1)令VT=;
2)对任意正规式R选择一个非终结符Z生成规则Z→R,并令S=Z;
3)若a和b都式正规式,对形如A →ab的规则转换成A →aB和B→b两规则,其中B是新增的非终结符;
4)在已转换的文法中,将形如A →a*b的规则进一步转换成A →aA|b;
5)不断利用规则3)和4)进行变换,直到每条规则最多含有一个终结符为止。
例:将R=(a|b)(aa)*(a|b)转换成相应的正规文法。
将l(l|d)*转换成相应的正规文法
1