64.有限状态自动机能识别(C) A.上下文无关语言B上下文有关语言C正规语言 D.0型文法定义的语言 65.己知文法G是无二义的，则对G的任意句型a(A) A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导，但他们对应的语法树相同 66.(B)不是DFA的成分 A有穷字母表B.多个初始状态的集合C多个终态的集合D.转换函数 67.与逆波兰式（后缀表达式）ab+c*d+对应的中缀表达式是(B) A.a+b+c*d B.(a+b)*c+d C.(a+b)*(c+d) D.a+b*c+d 68.后缀式bc-+-d+可用表达式(B)来表示。 A.(-(a+b)-c)+d B.-(a+(b-c))+d C.-(a-(b+c))+d D.(a-(-b+c))+d 69.表达式A*(B-C*(CD)的后缀式为B)。 A.ABC-CD/*+ B.ABCCD/*.+ C.ABC-*CD/ D.以上都不对 70.(D)不是NFA的成分。 A.有穷字母表 B.初始状态集合 C终止状态集合 D.有限状态集合 二、问答题 1.将文法GS)改写为等价的GS,使G'S不含左递归和左公共因子。 GSl:S→bSAe|bA A→Abld
64． 有限状态自动机能识别(C) A.上下文无关语言 B.上下文有关语言 C.正规语言 D.0 型文法定义的语言 65． 已知文法 G 是无二义的，则对 G 的任意句型α(A) A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导，但他们对应的语法树相同 66． (B)不是 DFA 的成分 A.有穷字母表 B.多个初始状态的集合 C.多个终态的集合 D.转换函数 67． 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B) A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d 68． 后缀式 abc−+−d+可用表达式(B)来表示。 A．(− (a+b)−c)+d B．−(a+(b−c))+d C．− (a−(b+c))+d D．(a−(−b+c))+d 69． 表达式 A*(B-C*(C/D))的后缀式为(B)。 A．ABC-CD/** B．ABCCD/*-* C．ABC-*CD/* D．以上都不对 70． (D)不是 NFA 的成分。 A. 有穷字母表 B. 初始状态集合 C. 终止状态集合 D. 有限状态集合 二、问答题 1． 将文法 G[S] 改写为等价的 G′[S]，使 G′[S]不含左递归和左公共因子。 G[S]： S→bSAe | bA A→Ab | d 答：
文法G$)改写为等价的不含左递归和左公共因子的GS]为： S-bB B-→SAelA A-→dA A'→bA'IE 2.将文法GS)改写为等价的GS],使GS]不含左递归和左公共因子。 GIS]:S-SAelAe A-→dAbAjdAd 李 文法GS]改写为等价的不含左递归和左公共因子的GS]为： S→AS S'→AeS'e A→dA' A'→ABE B-→bAE 3.将文法GS改写为等价的GS],使GS]不含左递归和左公共因子。 GIS]:S-A A→BAS B→aBa 答： 文法GS]改写为等价的不含左递归和左公共因子的G[S]为： S-IA A→BA A'→SA'E B→aB B'→BHE 4.判断下面文法是否为(1)文法，若是，请构造相应的山()分析表
文法 G[S] 改写为等价的不含左递归和左公共因子的 G'[S]为： S→bB B→SAe | A A→d A' A' →bA' | ε 2． 将文法 G[S] 改写为等价的 G'[S]，使 G'[S]不含左递归和左公共因子。 G[S]： S→SAe|Ae A→dAbA|dA|d 答： 文法 G[S] 改写为等价的不含左递归和左公共因子的 G'[S]为： S →AeS' S' →AeS'|ε A →dA' A' →AB|ε B →bA |ε 3． 将文法 G[S] 改写为等价的 G'[S]，使 G'[S]不含左递归和左公共因子。 G[S]： S→[A A→B]|AS B→aB|a 答： 文法 G[S] 改写为等价的不含左递归和左公共因子的 G'[S]为： S →[A A →B]A′ A′→SA′|ε B →aB′ B′→B|ε 4． 判断下面文法是否为 LL(1)文法，若是,请构造相应的 LL(1)分析表
s→aH H-→aMdld M-→Ab|E A→aMe 答： 首先计算文法的FIRST集和FOLLOW集如下表。 文法的FIRST集和FOLLOW集 非终结符 FIRST集 FOLLOW集 s (a) #) H (a d) #} fa e, d,b A (a e) (b) 由于predict(H-→aMd)npredict(H→d)={ayn{d}o predict (M-Ab)Npredict (M)=a,ed,b predict (A-aM)npredict (A-e)={ae 所以该文法是(I)文法，(I)分析表如下表。 d b →a H →aMd →d M -Ab →e →Ab A →aM e 5.判断下面文法是否为山1)文法，若是，请构造相应的山()分析表。 s→aD D-STele T一bHH H→de 答：
S→aH H→aMd | d M→Ab | ε A→aM | e 答： 首先计算文法的 FIRST 集和 FOLLOW 集如下表。 文法的 FIRST 集和 FOLLOW 集 非终结符 FIRST 集 FOLLOW 集 S {a}......... {# }... H {a ，d}..... {# }... M {a ，e ，ε} {d ，b} A {a ，e}..... {b}.... 由于 predict（H→aMd）∩predict（H→d）={a}∩{d }= predict（M→Ab）∩predict（M→ε）={a ，e}∩{d ，b }= predict（A→aM）∩predict（A→e）={ a }∩{ e }= 所以该文法是 LL(1)文法，LL(1)分析表如下表。 a d b e # S →aH. H →aMd →d. M →Ab. →ε →ε →Ab A →aM. →e. 5． 判断下面文法是否为 LL(1)文法，若是，请构造相应的 LL(1)分析表。 S→aD D→STe|ε T→bH|H H→d|ε 答：
首先计算文法的FIRST集和FOLLOW集如下表。 非终结符 FIRST集 FOLLOW集 s (a) (b.,d,e) D (a,s) {#,b,d,e} T (b,d, fe) H (d, e predict (D-STe)npredict (D-)=(a#b,d,e predict (T-bH)npredict (T-H)=(be predict (H-d)npredict (H-)=de 所以该文法是L(I文法，L(I)分析表如下表： a e 6 d s →aD -→STe →8 →E T →H →bH →H H →8 →d 6.判断下面文法是否为L(1)文法，若是，请构造相应的1)分析表。 S-→aD D-STele T-bM M-→blH H-M: 答： 文法的FIRST集和FOLLOW集 非终结符 FIRST集 FOLLOW集 s (a) #,b 0 (a c {#,b时 T b时 fe)
首先计算文法的 FIRST 集和 FOLLOW 集如下表。 非终结符 FIRST 集 FOLLOW 集 S {a} {#，b，d，e}. D {a，ε} {#，b，d，e } T {b，d，ε} {e} H {d，ε} {e} 由于 predict（D→STe）∩predict（D→ε）={a}∩{# ，b ，d ，e }= predict（T→bH）∩predict（T→H）={b}∩{e }= predict（H→d）∩predict（H→ε）={ d }∩{ e }= 所以该文法是 LL(1)文法，LL(1)分析表如下表： a e b d # S →aD. D →STe →ε →ε →ε →ε T →H. →bH →H. H →ε →d. 6． 判断下面文法是否为 LL(1)文法，若是，请构造相应的 LL(1)分析表。 S→aD D→STe|ε T→bM M→bH H→M|ε 答： 文法的 FIRST 集和 FOLLOW 集 非终结符 FIRST 集 FOLLOW 集 S {a}..... {# ，b} D {a ，ε} {# ，b} T {b}..... {e}