GATE CS 2003 Q15 — Undecidability

A language $L$ is recursive (decidable) if and only if its strings can be effectively enumerated in lexicographic (alphabetic) order.

1. Why is $L$ recursive?

To show that $L$ is recursive, we must design a Turing Machine (decider) that halts on all inputs and decides membership for any string $w$:

• If $L$ is finite, it is trivially recursive.
• If $L$ is infinite, we can run the lexicographic enumerator for $L$. Since the enumerator outputs strings in strictly increasing lexicographic order (first by length, then alphabetically):
• If the enumerator outputs $w$, we halt and accept.
• If the enumerator outputs a string lexicographically larger than $w$, we know $w$ will never appear. We halt and reject.

Since the enumerator is effective and the order is lexicographic, this decision procedure is guaranteed to terminate in finite steps for any string $w$. Thus, $L$ is recursive.

2. Why is $L$ not necessarily context-free?

There are many recursive languages that are not context-free. For example, the language $$L = \{a^n b^n c^n \mid n \ge 0\}$$ is recursive and can be easily enumerated in lexicographic order, but it is a well-known non-context-free language.

Therefore, $L$ is recursive but not necessarily context-free.