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.

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

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

Answer 2

Very important line-
REC has lexicographic enumeration procedure but RE do not have  lexicographic enumeration procedure (Of course, RE has  enumeration procedure, thats 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}$ genrates first string $w_1$
                M executes first step on $w_1$
$\tilde{M}$ genrates second string $w_2$
                M executes first step on $w_2$
                                  Second step on $w_1$
$\tilde{M}$ genrates 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?