GATE CSE 2003 | Question: 15

Question

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

• A. $L$ is necessarily finite
• B. $L$ is regular but not necessarily finite
• C. $L$ is context free but not necessarily regular
• D. $L$ is recursive but not necessarily context-free

Comments

L can be effectively enumerated means what? please i’m so confused

---

Can we consider it this way as well? after generation of language (in which ever order) if we can sort them in alphabetical order, then we can consider that language in the criteria mentioned by the question.

Note : 

1. We pass strings to machine, in any order, then we get output whether accepted or rejected by machine
2. Then we sort them aplhabetically
    

What are your thoughts sir? @Sachin Mittal 1@Arjun 

---

some Machine is effectively accepting strings of L in alphabetical Order
This means It has to decide whether the string is in alphabetical order or not
which makes L recursive
This can be done to even non context free languages as mentioned is best Answer

Answer 1

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

Since, the strings of $L$ can be enumerated it means $L$ is recursively enumerable. That is we have a TM which accepts all strings in $L$. Now, to be recursive the TM should reject all strings not in $L$. Since, the strings of the language can be enumerated in lexicographic order, it's easy to do this. 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.  This makes $L$ '''recursive'''.

 

Now, why  $L$ need not be context free or regular? Consider

 

$L = \{a^nb^nc^n \mid n\ge 0\}$

 

The strings of this language can be enumerated in lexicographic order. But we know $L$ is not context free as no PDA can accept $L$. 

Comments

@tuhin

this language is neither necessarily finite or infinite right ?

---

you are saying '' strings of L can be enumerated it means L is recursively enumerable''
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?

---

You are saying that we can tell whether a string is rejected by L or not by comparing it with the enumerated strings. But how will we compare this string lexicographically to the string s of L. I mean the algorithm can only tell the lexicographically order if the string belongs to L. So , if the string does not belong to L then how will we decide if some string is lexicographically greter than this not not.

Answer 2

Very important line:
REC has a lexicographic enumeration procedure, but RE does not have one.
(Of course, RE has an enumeration procedure — that’s why it is called a Recursively Enumerable language — but it need not be lexicographic.)

Throughout this answer, whenever I write RE, it means “RE but not REC”.

Why so?
For REC, we have a Halting Turing Machine (HTM).

Enumeration procedure for REC:
I can give each string to the HTM and wait for some time — either the HTM will accept it or reject it. If it accepts, print the string and move on to the next; if it rejects, move to the next string without printing. Of course, I can give strings in lexicographic order, and this procedure will enumerate them in the same order.

Here, \( \tilde{M} \) generates all strings in lexicographic order (or any desired order), and \( M \) outputs them in the same order.

---

Can we use the same procedure for RE?
(Again, RE means “RE but not REC”)

No! This procedure won’t work for RE. Why?

Repeat:
    \( \tilde{M} \) generates a string \( w \)
    \( M \) checks if \( w \in L \)
        If Yes → Print \( w \)
        If No → Ignore

 This procedure won’t work for RE because:

Problem: If \( w \notin L \), then \( M \) may loop forever.

---

The question is: How to enumerate RE? Which is the best procedure for enumerating RE?

We all know that there exists a procedure to enumerate RE, but we rarely bother about what it looks like 😄

Click to expand: Why we simulate giving all strings simultaneously

When we try to test strings one by one on a Turing Machine, there is a big problem: if one input takes too long to finish (say a million or even a billion but finite steps), we might get stuck on it forever and never reach the next input.

In other words, we cannot simply wait for one string to finish before starting the next, because that single string might run forever.

To solve this, we want to behave as if we are giving all strings to the Turing Machine simultaneously. This way, even if one string takes infinite time, the others can still make progress and get printed when accepted.

For example, if the 1st string takes 500 steps and the 2nd one takes only 5 steps, then after 5 steps the 2nd string gets printed first, and after 500 steps, the 1st string appears later.

\( \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 \)
    \( M \) executes 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 \)
    \( M \) executes third step on \( w_1 \)

And so on...

If for any string, the machine halts in a final state, it prints that string as output.

This procedure simulates “simultaneous execution” by giving each string a few steps one after another — a kind of round-robin process. This ensures that every string keeps progressing, and all strings that belong to the RE language will eventually be printed — even if some other inputs loop forever.

This procedure enumerates in a non-lexicographic (random) order.
For instance, if the 1st string takes \( 1000 \) steps and the 5th takes only \( 2 \) steps, the 5th string will be printed first.

---

Conclusion:
If someone says, “A language \( L \) can be enumerated by length if and only if it is recursive.” You must agree that this statement is true.

In short:
Regardless of the order, if a language can be enumerated in that order, it cannot be merely RE — it must be recursive.

Comments

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”. 

---

Like Dovetailing

Answer 3

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 

Comments

Ans is given as L is recursive...

---

@ indrajeet  yes . It is indeed option C. It was my mistake

Answer 4

The correct statement is D.

Here is the reasoning:

The phrase "effectively enumerated in lexicographic order" means that there is an algorithm (a Turing machine) that lists all the strings of the language $L$ in alphabetical order. This property is stronger than just being "recursively enumerable" (listable in any order).

This property directly implies that the language $L$ is recursive (also known as decidable).

 

Why it is Recursive (Decidable)

 

If a language $L$ can be enumerated in lexicographic order, we can construct an algorithm (a decider) that is guaranteed to halt and answer "YES" or "NO" for any input string $w$.

Here is the algorithm for the decider:

1. Take an input string $w$.

2. Start the ordered enumerator for $L$.

3. Compare $w$ to each string $s$ that the enumerator outputs.

   • Case 1: If the enumerator outputs $s$ and $s = w$, we halt and answer "YES" (the string is in the language).

   • Case 2: If the enumerator outputs $s$ and $s$ is lexicographically greater than $w$, we halt and answer "NO" (since the list is in order, $w$ will never appear).

This algorithm is guaranteed to halt for every possible input $w$, which is the definition of a recursive language.

 

Why it is "Not Necessarily Context-Free"

 

While $L$ must be recursive, it does not have to be context-free. Consider the classic example:

$L = \{a^n b^n c^n \mid n \ge 0\}$

• This language is recursive. A simple algorithm can scan a string and check if it has this form.

• It can be enumerated in lexicographic order. The enumerator can just check all strings in alphabetical order ($\epsilon$, a, b, c, aa, ab, ac... abc, ...) and print only the ones that match the pattern (it would print $\epsilon$, abc, aabbcc, etc.).

• However, this language is not context-free. It is the standard example of a language that fails the Pumping Lemma for context-free languages.

Since we have an example of a language that is recursive but not context-free, statement D is true. The other options are false because this same example, $L = \{a^n b^n c^n\}$, is infinite (rules out A) and not regular (rules out B).

Answer 5

(A.) L is necessarily finite

      Contradicting Example : L = {a,aa,aaa, ...}

(B.) L is regular but not necessarily finite

      Contradicting Example : L = {ab,aabb,aaabbb, ...}

(C.) L is context free but not necessarily regular

      Contradicting Example : L = {abc,aabbcc,aaabbbccc, ...}

 

Notice that all contradicting examples are enumerated in lexicographical order

Hence (D). should be the only correct option. 

Although it is not good to always rely on such a method of answering question via contradicting examples, because note we have not analyzed option D thus we missed a point to improve upon our conceptual understanding. But from exam point of view, whatever it takes.

Answer 6

OPTION D is the answer

Lets see why this is correct answer. Its given that there is a enumerater (turing machine) thus its recursively enumerated language. now since there is a turing machine which literally prints all the strings in the lexographical order say aa,ab,bb,.. over the alphabet = {a,b}. now lets check for members: if we want to find abbb in this list then it must be in a finite position bcz of the lexographical order. so we can run this machine and figure it out. now for the non members if we are traversing and figure out there is a lexographically larger string than the current one then we halt and reject it. for eg if the list is like aa,ab,bb and if we are searching for ba, when we reach bb we can be sure that ba should have been before this bb and we can reject this input. 

hope its useful for all of u.