对于下面所给的文法:G1=({S,A,B,C, D}，{a, b, c, d},P1,S)P1由如下产生式组成:S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB以及G2=({S,A,B,C,D}，{a, b, c, d} ,P2,S)P2由如下产生式组成:S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d对于G1，构造一等价的左线性文法G1’;对于G2构造一等价的右线性文法2’。
举一反三
- 对于下面所给的文法:G1=({S,A,B,C, D}，{a, b, c, d},P1,S)P1由如下产生式组成:S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB以及G2=({S,A,B,C,D}，{a, b, c, d} ,P2,S)P2由如下产生式组成:S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d试分别对G1和G2构造相应的状态转换图(提示:对于右线性文法，可将形如C→D的产生式视为C→e D;而对左线性文法，则可将它视为C→D e )。
- 对于下面所给的文法:G1=({S,A,B,C, D}，{a, b, c, d},P1,S)P1由如下产生式组成:S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB以及G2=({S,A,B,C,D}，{a, b, c, d} ,P2,S)P2由如下产生式组成:S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d试给出若干个不能由G1或G2产生的符号串，并验证它们同样不能用G1'和G2′产生。
- 给定正规文法为G[S]： S→aB｜bA A→aC｜bA B→bE｜dD｜cB C→cB｜bF｜dD D→aC E→bE｜ε F→bE｜ε （1）构造与G[S]等价的NFA。 （2）将所得NFA确定化为DFA。 （3）将DFA最小化。 （4）将最小化后的DFA转换为等价的正规式
- 对于文法G(S')，该文法识别活前缀的DFA如下图，状态I2包含的项目有G(S')：(0) S' → S(1) S → Pa(2) S → Pb(3) S → c(4) P → Pd(5) P → Se(6) P → f[img=3601x1590]1803958e6ecda94.png[/img] A: S → Pa B: S → Pb C: S → Pc D: S → Pd
- 对下面文法的生成式，找出其正则式G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→cC A→bBB→bB B→aC→D C→abBD→d A: ab+a|acd|acab+a|b*a B: ab*a|acd|acab+a|b*a C: ab*a|acd|acab*a|b*a D: ab+a|acd|acab+a|b+a