(编译原理)求下述文法对应正规式：S->0A|1BA->1S|1B->0S|0

Question

(编译原理) 求下述文法对应正规式：S->0A|1B A->1S|1 B->0S|0

Answer 1

一、简单的推导思路
1、该文法的对应正规式为：[01|10]+
2、推导：
（1）首先,展开产生式S,可知S要么以0开头,要么以1开头；
（2）如果S按产生式S->0A展开,则S必以01开头,因为通过产生式A->1S|1可知,A必定是以1开头的；
（3）如果S按产生式S->1B展开,则S必以10开头,因为产生式B必定以0开头；
（4）综上,可知,S是以01或10开头的非终结符号；
（5）当A以产生式A->1展开或 B以B->0展开时,S将推导结束；
（6）当A以产生式A->1S展开或 B以B->0S展开时,产生式中的非终结符号S将重复（1）-（3）的推导步骤；
（7）综上所述,该文法的对应正规式为：[01|10]+.
二、联立方程组求解
假设非终结符号S、A、B都分别代表一个正规式,则正规文法的产生式集合所代表的就是关于正规式S、A、B的一个方程组.
我们将文法“|”符号替换为正规式“+”符号,可得,
S=0A+1B=0(1S+1)+1(0S+0)=01(S+ε)+10(S+ε)=(01+10)(S+ε)=(01+10)S+(01+10).
根据方程X=rX+t有形如X=r*t的解论断,可得,
S=(01+10)*(01+10)=[01|10]+.