Question

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

Answer 1

Answer to Question#38609 – Math – Other

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

Solution:

Since L can be effectively enumerated so L has to be regular, but is doesn't mean that the decisions are finite.

Hence (B) is correct option.

Answer: (B) L is regular but not necessarily finite