10,146 views

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

1. $L$ is necessarily finite
2. $L$ is regular but not necessarily finite
3. $L$ is context free but not necessarily regular
4. $L$ is recursive but not necessarily context-free

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.

Recursive language is definitely can be enumerated in lexicographic order, and recursively enumerable language is effectively enumerated but may not be guaranteed lexicographic order.
This was in Made easy test series.

### Subscribe to GO Classes for GATE CSE 2022

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$.
by

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

@arjun sir, can u give an example of language which is not csl but recursive ?
edited by
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 anbncn 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?
edited
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???
edited
@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.

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.

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

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.

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.

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

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

edited by

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

by

Ans is given as L is recursive...

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

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

L={anbncn | n0}

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={0n1n} . 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 anbncn we will generate abc before aabbcc which is ordered by increasing length. Do we consider it in lexicographical order?