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→Abld64． 有限状态自动机能识别(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 答：