-
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
-
- L is necessarily finite
- L is regular but not necessarily finite
- L is context-free but not necessarily regular
- L is recursive but not necessarily context-free
- L is necessarily finite
Correct Option: D
The strings of a language L can be effectively enumerated means a Turing machine exists for language L which will enumerate all valid strings of the language. If the string is in lexicographic order then TM will accept the string and halt in the final state.
But, if the string is not lexicographic order then TM will reject the string and halt in non-final state. Thus, L is recursive language. We cannot construct PDA for language L. So, the given language is not context free. Thus, option (D) is correct.
