options mismatch from original paper. chek this

If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

- $L$ is necessarily finite
- $L$ is regular but not necessarily finite
- $L$ is context free but not necessarily regular
- $L$ is recursive but not necessarily context-free

### 5 Comments

For two strings s1 and s2, we have that s1 < s2 in lexicographical ordering if |s1| < |s2| or |s1| = |s2| then s1 appears before s2 in the dictionary ordering. (That is, lexicographical ordering is a dictionary ordering for strings of the same length, and shortest strings appear before longer strings.)

A language L is TM recognizable iff it can be enumerated.

A language L is decidable iff it can be enumerated in lexicographic order.

## 4 Answers

Answer is (**D**) $L$ is recursive but not necessarily Regular or not even context-free.

### 30 Comments

Using this decided we can create lexicographic order enumerator even for any recursive language, even if it is not CSL. So we can say that L is recursive but not necessarily Regular or not even context-free/context sensitve.

But if we have the enumeration procedure along with some order which can help us to distinguish between strings in the language and strings not in the language, then the language is recursive right?

If i take aaabbbccc and aabbcc ,now first is higher lexograhic order than second.So what exactly does your above statement says?

I think the below statement is not correct.

If i take aaabbbccc and aabbcc ,now first is higher lexograhic order than second

**lexicographical ordering is a dictionary ordering for strings of the same length, and shortest strings appear before longer strings.**

So in ordering aabbcc should come before aaabbbccc.

Please refer this page 5: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf

@Srestha:- For any word w, if we see a word in the enumeration which is lexicographically higher than w but no w, it means w is not in the language

For this line,can you give a any example and tell what it is trying to say?I am not able to understand this point.

@rahul

lexicographic order means only dictionary order, nothing more than that

In sorting that is why we sort each and every element for lexicographic ordering

See this https://gateoverflow.in/1762/gate2012_39

just see one thing ,merge sort is working as normal merge sort for lexicographic ordering

@Srestha:I understand lexograhic order.But i dont understand the statement arjun sir gave above:(

The following statment i am talking about

:- For any word w, if we see a word in the enumeration which is lexicographically higher than w but no w, it means w is not in the language

Now as per example given, aaabbbccc , aabbcc belongs to language.

aaabbbccc is having higher order than aabbcc.

Now w=aaabbbccc ,and i see a word aabbcc which is higher order than w but no w.So w (aabbcc) wont belong to language?Where i am going wrong/

Because if y is having less lexographic order than X. if we see 3rd bit,then y comes first and x comes after that.So,how can i stop ?

If i see langiage $a^nb^nc^n$ , $L ={abc, aabbcc,aaabbbccc,aaaabbbbccccdddd.......................}$, so here dont you think abc has the highest lexographic order ,because its second bit is b and for others the second bit is a and they must come first in lex oredrering?

I hope you get my point:(

So how can we traverse infinite strings?I may be wrong !

we know that any language is a subset of sigma*,since sigma* is countable therefore every particular language is countable.and since if a language is countable, therefore there must exist an enumeration method which could genarate all the strings of the language.

acc. to you, strings of L can be enumerated it means L is recursively enumerable,therefore every language should be recursively enumerable.which is not true.

please tell me where i am going wrong?

Very important line-

REC has lexicographic enumeration procedure but RE do not have lexicographic enumeration procedure (Of course, RE has enumeration procedure, that is why it is called Recursively enumerable language but it need not to be lexicographic )

(Throughout this answer, whenever I write RE it means "RE but Not REC")

Why so ?

-for REC we have Halting Turing machine.

Enumeration procedure for REC-

I can give each string in HTM and wait for some time, either HTM will accept it or reject it. If accept it then print string and move on to next string, if reject then move to next string without printing.

Of course i can give strings in lexicographic order and this procedure will enumerate in the same order in which i give input.

Here$ \tilde{M}$ generates all strings in lexicographic order (or in whatever order we want) and M also outputs in same order.

Can we use same procedure for RE ? (again RE means "RE but not REC")

NO!, this procedure won't work for RE, Why?

That enumeration procedure looks like this-

Repeat: $ \tilde{M}$ generates a string w

M checks if w∈L

Yes: Print w

No: Ignore

This procedure won't work for RE.

Problem: If w∉L M may loop forever

Now, The question is, How to enumerate RE ?, Which is best procedure for enumerating RE ?

-We all know that there is a procedure to enumerate RE, but we never bother about how this procedure looks like :D

I have one idea, not sure if this works or not, Let's see-

-I give all strings to TM simultaneously, and as soon as one string is accepted by TM, It will print.

Say, 1st string is taking 500 steps and 2nd string is taking 5 steps then after 5 steps it will print 2nd string, and after 500 steps it will print 1st string.

Seems like it will work and will enumerate strings of RE language, but How can i give all strings simultaneously?

-If i modify the procedure mentioned above then it will pretend like all strings are given simultaneously.

$\tilde{M}$ generates first string $w_1$

M executes first step on $w_1$

$\tilde{M}$ generates second string $w_2$

M executes first step on $w_2$

Second step on $w_1$

$\tilde{M}$ generates third string $w_3$

M executes first step on $w_3$

M executes second step on $w_2$

Third step on $w_1$

And So on....

If for string machine halts in a final state then it prints on the output.

This procedure enumerates in random order.

Say, 1st string is taking 1000 steps of TM and 5th takes only 2 steps. Then it prints 5th string first.

Now if i ask you "A language L can be enumerated by length if and only if it is recursive.", Then You must agree that this statement is also true.

Be it any order, if u can enumerate in that order then that language can not be RE.

### 4 Comments

Best Explanation!!!

Though I have understood this question as well as your answer properly, Bhai please confirm that I am understanding the term** There exists lexicographic enumeration Procedure **correctly.

According to my understanding.

"There exists lexicographic enumeration Procedure " means we can print all strings accepted by M in lexical order.

Am I thinking correctly????

Thank you, Bhai :)

Can you please help me in this question also:-

https://gateoverflow.in/138444/theorem-example-https-nakhleh-comp481-final_review_sp06_sol#c138465

Be it any order, if u can enumerate in that order then that language can not be RE.

there is something wrong in this statement, right?

If we can order the enumeration then it will be Recursive.

And if we can’t order the enumeration then it will be RE.

I think you mean to say that it can’t be “recursively enumerable without being recursive”.

Assume $M_R$ is a Turing recognizer and $M_E$ is a Turing Enumerator for a language L

=> If w belongs to L and we give w as input to $M_R$, it will accept.

=> With the help of $M_R$, $M_E$ will test each string of $\sum ^{*}$ (dovetailing) one by one (attempt shorted to longer strings) and whenever a string gets accepted by the $M_R$, $M_E$ will print it.

So, above we are only talking about member strings. We don't know what will happen to non-member strings of L. Non-member strings may get rejected by $M_R$ or TM itself go into an infinite loop (hang). So, we can only comment about the semi-decidability of the language if some enumerator prints it's member strings. [Here we are not having any guaranty of printing in lexicographic order, longer strings might get accepted before longer strings because of dovetailing procedure ]

Now if we say about the lexicographic order. To print effectively we don't need to apply dovetailing here. Start with shorter strings and accept it (if a member) and reject it if not and keep doing this. The acceptance and reject make the language Recursive.

*L is recursive but not necessarily Regular *

### 2 Comments

### 10 Comments

okay :) You got the meaning of lexicographic order wrong. It means alphabetic order OF STRINGS IN L. For example L can be {a, ba, ab}, lexicographic ordering of L will be {a, ab, ba}. For {abb, aa}, the order will be {aa, abb}. Similarly for any L, we can have a lexicographic ordering. You are considering the case when L = Σ* only.

http://www.cs.duke.edu/courses/spring05/cps140/lects/sectRecEnumH.pdf