Multiple choice

If the strings of the language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?

  1. L is necessarily finite.

  2. L is regular but not necessarily finite.

  3. L is context free but not necessarily regular.

  4. L is recursive but not necessarily context free.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

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 can not construct PDA for language L. So, the given language is not context free.

Keep practicing — related questions