文库摘要：

文库分享网（www.Wkfxw.com），全免费下载

(1) 把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：
S → AB
A → aAb|ab
B → cB|
(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：
S → aE|Ea|bSS|SbS|SSb
E → aEbE|bEaE|
(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）：
S → aSBS|BSaS
B → b|bb
(4) 解法一：
S →〈奇数头〉〈整数〉〈奇数尾〉
         |〈奇数头〉〈奇数尾〉
         |〈奇数尾〉
  〈奇数尾〉→ 1|3|5|7|9
  〈奇数头〉→ 2|4|6|8|〈奇数尾〉
  〈整数〉→ 〈整数〉〈数字〉|〈数字〉
  〈数字〉→ 0|〈奇数头〉
解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)
S→AB | B
A→AC | D
B→1|3|5|7|9
D→2|4|6|8|B
C→0|D
(5) 文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9 },S,P)
S→N0 | N5
N→MD|
M→1|2|3|4|5|6|7|8|9
D→D0 | DM |
(6) G[S]：S→aSa | bSb | cSc | a | b | c |
8. 解答：
(1) 句子abab有如下两个不同的最左推导：
S => aSbS => abS =>abaSbS => ababS => abab
    S => aSbS => abSaSbS => abaSbS => ababS => abab
    所以此文法是二义性的。
(2) 句子abab的两个相应的最右推导：
    S => aSbS => aSbaSbS => aSbaSb => aSbab => abab
    S => aSbS => aSb => abSaSb => abSab => abab
(3) 句子abab的两棵分析树：