Match the following : \(\begin{array}{clcl} & \textbf{List – I} & &…
2015
Match the following :
\(\begin{array}{clcl} & \textbf{List – I} & & \textbf{List – II} \\ \text{(a)} & \{a^n b^n \mid n > 0\} \text{ is a deterministic } & \text{(i)} & \text{but not recursive language}\\ & \text{ context free language} \\ \text{(b)} & \text{The complement of }\{a^n b^n a^n \mid n>0\} & \text{(ii)} & \text{but not context free language}\\ & \text{is a context free language} \\ \text{(c)} & \{a^nb^na^n\}\text{ is a context sensitive} & \text{(iii)} & \text{but cannot be accepted by a } \\& \text{ language} && \text{deterministic pushdown }\\ &&& \text{automaton} \\ \text{(d)} & \text{L is a recursive language} & \text{(iv)} &\text{but not regular} \\ \end{array}\)
Codes :
- A.
(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
- B.
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
- C.
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
- D.
(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
Attempted by 49 students.
Show answer & explanation
Correct answer: C
Correct matching (with brief reasons):
(a) {a^n b^n | n>0} is a deterministic context-free language — but not regular.
(b) The complement of {a^n b^n a^n | n>0} is a context-free language — but cannot be accepted by a deterministic pushdown automaton.
(c) {a^n b^n a^n} is a context-sensitive language — but not context-free.
(d) The statement about L should read "recursively enumerable" (r.e.) if it is to match "but not recursive language"; as printed "L is a recursive language" contradicts "but not recursive language." If intended as r.e. but not recursive, then it pairs with that qualifier.
Summary mapping: (a) → "but not regular"; (b) → "but cannot be accepted by a deterministic pushdown automaton"; (c) → "but not context free"; (d) → "but not recursive" (only if the intended property is recursively enumerable).