第1个回答 推荐于2016-12-02
一、简单的推导思路
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]+。本回答被提问者采纳