GATE2003-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

options mismatch from original paper. chek this

http://www.questionpapers.net.in/Question%20Papers/gate-question-papers-download/gate-question-papers-download-computer-sciences-2003.pdf

http://quiz.geeksforgeeks.org/gate-cs-2003/

---

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.

---

https://cs.stackexchange.com/questions/56822/if-the-strings-of-a-language-can-be-enumerated-in-lexicographic-order-is-it-rec

---

Recursive language is definitely can be enumerated in lexicographic order, and recursively enumerable language is effectively enumerated but may not be guaranteed lexicographic order.

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

Can we say it is not even CSL ? I mean defination of  Recursive language is that it can say we can say yes / no to every string.

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.

---

yes, we can..

---

how can we say if L can be enumerated it means L is recursively enumerable.??

please explain.

---

@arjun sir, can u give an example of language which is not csl but recursive ?

---

I think the strings of the language you quoted cannot be enumerated in a lexicographic order. According to lexicographic ordering aa < ab. So in this case aabbcc will come in enumeration procedure before abc. So what's the enumeration procedure for this language then. If it can be which is the first string in the enumeration procedure?

---

^Yes, the ordering must give higher preference to string length.

---

So aⁿbⁿcⁿ is not enumerable lexicographically right? We have to proceed with 3 length first,then 6 and so on which is not lexicographic.

So doesn't this imply that language should be finite?

---

@arjun sir can u plz simplify these two lines

"For any word ww, if we see a word in the enumeration which is lexicographically higher than ww but no ww, it means ww is not in the language.  This makes L '''recursive''"

---

@ Arjun Sir, that means if we have only the enumeration procedure for strings belonging to some language, then the language is Recursively Enumerable

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?

---

Lexicographic order means dictionary order or alphabetical order. Therefore $aabbcc$ will surely come before $abc$, and we don't have to give higher preference to the length of string. Nevertheless, as $CFL$ are a proper subset of $REC$, that means there exist $REC$ languages which are not $CFL$, therefore answer is option D.

---

Will it be CSL too???

---

@Arjun Sir.Can you explain this line:- For any word w, if we see a word in the enumeration which is lexicographically higher than w but no w, it means ww is not in the language.

 

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

---

@rahul

how aabbcc in ww

what is w there?

---

Typeo. Its is w and not ww.I copied that line from answer.I think it was copied wrongly.
Anyhow, Can you please help in understanding the meaning of this line?

---

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

---

yes

@rahul

It means u r finding aabbcc and still not get, and next string is aaabbbcccc

So, obviously u can ay, aabbcc is not inside language L

Isnot it?

---

@Tuhin.In dictionary, we follow lexograhic order.But it does not mean that all words are of same length.

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

---

It will be like w=abc

and the next string def which is higher than w but no w

---

@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/

---

@rahul

why r u thinking , it is wrong?

I think u r going right. Actually here 'yes' and 'no' ans is possible. So, that is why language is recursive

---

But both aaabbbccc and aabbcc are in language.

As per Arjun sir statement,

 Now,w=aaabbbccc ,and i see a word aabbcc which is higher order than w but no w.Means , i see a word with higher lexographic order than w ,but it is not w,so it says w wont belong,but here w belongs.

---

in dictionary if u searching for a word starting with aab (as w=aabbcc)

and then u go upto aaabbbccc then it mustnot be higher order than the word u r searching for, right?

---

If i search for x=aabbcc , then if i encounter y=aaabbbccc,then i should not stop.

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:(

---

yes that is right

 abc higher order than aabbcc

but I think abc contains a part of  aabbcc

So, no w part is not satisfies here

so, higher order of abc and no w should be def

should it not?

---

It means for saying aabbcc is in my language,i have to traverse infinite strings?Becasue there are infinite strings who are less lexographic number than aabbcc,which can be aaabbbccc,aaaabbbbccccdddd,aaaaabbbbbccccc............(all strings in language with more than 3 a will have less rank than aabbcc and then there is a chance of getting aabbcc(3rd position b)).

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

---

@rahul
CSL can take infinite string
even CFL can take infinite string
So, why not recursive can take?
Finite string only for regular language

---

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

Comments

@ Sachin Mittal 1

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????

---

In whatever order $\tilde{M}$ is producing input, $M$ is taking input in that order only.

If $ \tilde{M}$ is producing (enumerating) in lexicographic order and $M$ is Halting TM then $M$ will also accept everything in order.

---

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

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

option A. L is regular. nfa is possible n simple to draw.and there is no limitation on the number of "a" or no. of "b".

Comments

L={aⁿbⁿcⁿ | n≥0}

This language satisfies the given conditions but is not regular rt?

---

you right bt the L you have mentioned is only a part of the L we are discussing . like u can think of L=(0+1)^* and L1={0ⁿ1ⁿ} . L includes L1 but other strings also that makes L regular.

---

"Part of a language we are discussing"

The question is for ANY language, which can be enumerated in lexicographic order. And so, any one counter example is enough to prove that it is non-regular.

---

plz think of it like this,  any no. of a followed by ne no. of b's or ne no. of c's or ne no.of d's.... n so on

---

That's another language which can be enumerated in lexicographic order and which is regular. So?

---

thats the same lang that has been asked in the 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 ?"

This is the question.

---

with all due respect i m still see both as same lang(L)

---

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

---

Sir in case of aⁿbⁿcⁿ we will generate abc before aabbcc which is ordered by increasing length. Do we consider it in lexicographical order?