对于下面所给的文法: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 )。
解[img=426x223]17e09d9415ec0e2.png[/img][img=419x174]17e09d95290b9ea.png[/img]
举一反三
- 对于下面所给的文法: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产生的符号串，并验证它们同样不能用G1'和G2′产生。
- 对下面文法的生成式，找出其正则式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
- 对于文法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→abS A→bBB→b B→cCC→D D→bBD→d A: (aab)*(ab|ε)(cb)*(cd|b) B: (aab)*(ab|ε)*(cb)*(cd|b) C: (aab)*(ab|ε)(cb)(cd|b) D: (aab)*(ab|ε)(cb)*(cd|b)*
内容
- 0
设已给文法G=(VN,VT,P,s)，其中，P仅含形如A→ a BA→ a a EV*T，BEVN的产生式，试证明:由此种文法所产生的语言是一正规语言。
- 1
给定正规文法为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转换为等价的正规式
- 2
试判断原子态：1s1s3S1,1s2p3P2,1s2p1D1,2s2p3P2中，下面哪组是存在的？ A: 1s1s3S1,1s2p3P2; B: 1s2p3P2,1s2p1D1; C: 1s2p3P2,2s2p3P2; D: 1s1s3S1,1s2p1D1;
- 3
能够产生语言[img=527x63]1803448d4175907.png[/img]的文法是 A: 文法G(S): S → AC A → aAb | ab C → cC | c B: 文法G(S): S → AC A → aAb | ab C → cC | ε C: 文法G(S): S → AC | A A → aAb | ab C → cC | c D: 文法G(S): S → AC A → aAb | ε C → cC | ε
- 4
电子组态1s2p所构成的原子态为（ ）。 A: 1s2p1S0，1s2p1P1, 1s2p3S1 1s2p3P2,1,0 B: 1s2p1S0，1s2p1P1 C: 1s2p1S0，1s2p3S1 D: 1s2p1P1，1s2p3P2,1,0