# If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?

Lexicographic order is not such a good order since its order type is not $$\omega$$. Instead of explaining formally what that means, let me give an example. Consider the language $$(a+b)^*$$. If you enumerate the words in lexicographic order, you get $$\epsilon, a, aa, aaa, \ldots, ab, \ldots$$ The first $$\ldots$$ signify infinitely many terms. So it isn't really clear what it means to enumerate a language in lexicographic order. There could be two interpretations: either the language $$L$$ doesn't suffer from this problem, or you really mean a slightly different order. Since the precise answer doesn't matter for all that follows, we will just assume that you can effectively enumerate $$L$$ in some (effective) order whose order type is $$\omega$$ (i.e., when the problem above doesn't happen).
The proof that $$L$$ is recursive can be a bit subtle, due to a certain ambiguity: what happens if $$L$$ is a finite language? There are two reasonable interpretations of effective enumerability in this case: either the enumerator will eventually halt, or it won't, but at some point would stop outputting strings. Fortunately, this ambiguity doesn't affect the proof.
For the proof that $$L$$ is recursive, we consider two cases. If $$L$$ is finite, then it is trivially recursive. If $$L$$ is infinite, then to decide whether $$x \in L$$ and wait until either $$x$$ is output, or a string larger than $$x$$ is output (if $$x \notin L$$ then this will happen eventually since $$L$$ is infinite). In the first case $$x \in L$$, in the second $$x \notin L$$.
To see that $$L$$ is not necessarily context-free, you can consider your favorite non-context-free language $$\{c^nb^na^n : n \geq 0\}$$ which is effectively enumerable in (plain vanilla) lexicographic order.
• $\epsilon,abc,a^2b^2c^2,a^3b^3c^3,\ldots$ – Yuval Filmus Dec 9 '19 at 14:14
• ok sorry for deleting comment, but shouldn't $aabbcc$ precede $abc$. because tha't what lexicographic order is right? – Vimal Patel Dec 9 '19 at 14:16
• Consider the order $c < b < a$ on letters. – Yuval Filmus Dec 9 '19 at 14:18