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?


1 Answer 1


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.

  • $\begingroup$ $\epsilon,abc,a^2b^2c^2,a^3b^3c^3,\ldots$ $\endgroup$ Commented Dec 9, 2019 at 14:14
  • $\begingroup$ ok sorry for deleting comment, but shouldn't $aabbcc$ precede $abc$. because tha't what lexicographic order is right? $\endgroup$ Commented Dec 9, 2019 at 14:16
  • $\begingroup$ Consider the order $c < b < a$ on letters. $\endgroup$ Commented Dec 9, 2019 at 14:18
  • $\begingroup$ Ok got it. Thanks. $\endgroup$ Commented Dec 9, 2019 at 14:18
  • $\begingroup$ How would you compare a string $x \notin L$ with the enumerated strings? We are only assuming an ordering on $L$. $\endgroup$ Commented May 31, 2022 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.