0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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 $\{a^nb^nc^n : n \geq 0\}$ which is effectively enumerable in (plain vanilla) lexicographic order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy