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 51 students.
Show answer & explanation
Correct answer: C
Concept: formal languages form a strict hierarchy — Regular ⊂ Deterministic Context-Free ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursive ⊂ Recursively Enumerable — and two closure facts pin down this match: (1) deterministic context-free languages are closed under complementation, so if a language's complement were deterministic context-free, the language itself would have to be deterministic context-free as well; and (2) every context-sensitive language is decided by some linear-bounded automaton, so it is always recursive.
Applying it to each row:
(a) anbn is the standard example of a deterministic context-free language — a deterministic pushdown automaton pushes the a-block and pops one symbol per b to check the counts match. It still fails the pumping lemma for regular languages (pumping the a-block unbalances the counts), so it is not regular.
(b) the complement of anbnan (n≥1) is context-free: over {a,b}, it splits into finitely many pieces that are each regular or context-free — strings that don't even fit the a*b*a* pattern (regular), strings that fit the pattern with two blocks of unequal length (context-free, one stack suffices per comparison), and the single boundary string ε itself, which falls outside n≥1 (finite, hence regular). A finite union of context-free pieces is context-free, so the whole complement is context-free. It cannot be deterministic, because DCFLs are closed under complementation — if this complement were deterministic, anbnan itself would be deterministic context-free, which it is not — so it cannot be accepted by a deterministic pushdown automaton.
(c) anbnan is context-sensitive (a linear-bounded automaton can verify all three block counts using its bounded working tape as scratch space) but fails the context-free pumping lemma (any pumped substring unbalances at least one of the three blocks), so it is not context-free.
(d) with (iv), (iii) and (ii) already placed against (a), (b) and (c), the only label left is (i), “but not recursive language.”
Cross-check: all four List–II labels are used exactly once, so this is a valid one-to-one match, and it agrees with the published answer key for this UGC NET (Computer Science) December 2015 paper. One wording point worth flagging honestly: item (d) is printed in the original paper as “L is a recursive language,” and read alone, pairing it with “but not recursive language” looks self-contradictory. That wording has been checked against the archived exam paper and is kept exactly as officially printed rather than silently changed to “recursively enumerable” (which would read more smoothly) — the official key still resolves (d) to the one label left over once (a), (b) and (c) are correctly placed, so the scored mapping is unaffected by the wording quirk.
Correct matching: (a)-(iv), (b)-(iii), (c)-(ii), (d)-(i).