Test by Bikram | Theory of Computation | Test 1 | Question: 25

Question

If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language.

• A. Regular   
• B. CFL but need not be regular      
• C. CSL but need not be a CFL      
• D. Recursive but need not be a CSL

Comments

can u explain this question plz? sir

---

@arjun sir, you say " enumerate all strings in alphabetic order for length ll and then do the same for l+1l+1 and so on. This is not actually dictionary order." But this is only the definition of lexographic or dictionary order, isn't it? Please explain.
Also, answer says need not be csl. So how to know which language can be lexographically ordered and which not?

---

Can I assume that every string in language eventually will be generated.

If that is not the case than I suspect that language might not be recursively enumerable.

Answer 1

@shraddha Is it? In dictionary b comes after aab rt? But I assume this is defined somewhere.

If we can lexicographically order the strings we can get a TM for accepting the strings in the language and rejecting the strings not in the language. But still there is no guarantee that the amount of tape space required for this is linear in terms of the input which is the condition for a language to be CSL.

Comments

Sir but we can make a DFA such that 

It accepts strings in lexographical order