How to prove the statement

"If the strings of a language $L$ can be enumerated in lexicographically(alphabetic) order, then the language is Recursive but not context free" ?

Basically, My point is how can the strings of $a^nb^nc^n$ can be lexicographically enumerated as first $n$ has infinite terms .

  • 2
    $\begingroup$ I can't see how $a^nb^nc^n$ is related to proving the first statement. What is the actual question here? How to prove the statement (1) or how to apply the statement to $a^nb^nc^n$ (2) ? $\endgroup$ – chi Apr 5 '17 at 13:16
  • $\begingroup$ The sequence $a^nb^nc^n$ has no infinite terms. The $n$th term has length $3n$. $\endgroup$ – Yuval Filmus Apr 5 '17 at 13:17
  • $\begingroup$ Presumably the question asks you to prove that a specific language $L$, namely $L = \{a^nb^nc^n : n \geq 0\}$, is recursive but not context-free. $\endgroup$ – Yuval Filmus Apr 5 '17 at 13:18
  • $\begingroup$ @YuvalFilmus Presumably the quoted question is the actual question. I suspect that Garrick is confused because s/he thinks that $a^nb^nc^n$ is a counterexample to the thing s/he's been told to prove. $\endgroup$ – David Richerby Apr 5 '17 at 17:36

Your confusion may stem from the interpretation of "lexicographically". It's common to take this to mean "by length and then for strings of the same length, by alphabetic order. If this is the case, then an enumeration of your language would be: $\epsilon, abc, aabbcc, aaabbbccc, \dotsc$.

If your language was $\{a^ib^jc^k\mid i,j,k\ge 0\}$ then the enumeration would be $$ \epsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aab, \dotsc $$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.