第十章 下推自动机与CFG化简规范--习题【含答案】 软件理论基础

(1)单选题

考虑下面的上下文无关文法:

可空符号集合为()

A  {S,C}

B  {S,A,B,C}

C  {S,A,C}

D  {A,B,C}

(2)单选题

第一题CFG消除产生式之后,所有的单一偶对为()

A  (A,C)(C,S)

B  (A,C)(C,S)(B,S)

C  (A,C)(C,S)(B,S)(A,B)

D  {S,A,B,C}中任意一对符号都为单一偶对

(3)单选题

第一题CFG消除产生式和单一表达式之后,无用符号为:

A  A

B  B

C  C

D  S

(4)单选题

下面说法正确的是()

A  终态型DPDA和空栈型DPDA的表达能力不同

B  空栈型NPDA和终态型NPDA的表达能力不同

C  空栈型DPDA和DFA的表达能力相同

D  终态型DPDA和NFA的表达能力相同

(5)单选题

下列语言满足前缀性质的是()

A  {a*}

B  {a, ab, abc}

C  {w2w^R | w∈{0,1}*}

D  {ww^R | w∈{0,1}*}

(6)单选题

判断下列说法是否正确:存在CFL,不能被任意一个终态型DPDA接受。

A  错误

B  正确

(7)单选题

如果对于某个DPDA P有L=N(P),则

A  L具有前缀性质,且存在DPDA P‘满足L=N(P’)

B  L不具有前缀性质,但存在DPDA P‘满足L=N(P’)

C  L不具有前缀性质,也不存在DPDA P‘满足L=N(P’)

D  L具有前缀性质,但不存在DPDA P‘满足L=N(P’)

获取标准答案请阅读全文

隐藏内容 需要支付:¥7

未经允许不得转载!第十章 下推自动机与CFG化简规范--习题【含答案】 软件理论基础