If the strings of a language L can be effectively enumerated in lexicographic…
2003
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ?
- A.
L is necessarily finite
- B.
L is regular but not necessarily finite
- C.
L is context free but not necessarily regular
- D.
L is recursive but not necessarily context free
Attempted by 8 students.
Show answer & explanation
Correct answer: D
A language whose strings can be effectively enumerated in lexicographic order implies that there exists a Turing machine that can list all strings of L in alphabetical order. This means the language is recursively enumerable and, since enumeration is effective, it must be recursive (decidable). However, not all recursive languages are context-free; for example, {a^n b^n c^n | n ≥ 0} is recursive but not context-free. Therefore, L must be recursive but not necessarily context-free, making option D correct.
A video solution is available for this question — log in and enroll to watch it.