options mismatch from original paper. chek this

The Gateway to Computer Science Excellence

+39 votes

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

+7

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.

+97 votes

Best answer

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

+2

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.

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.

+1

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?

+2

So a^{n}b^{n}c^{n} 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?

+2

@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''"

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

0

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

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?

0

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.

0

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

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

0

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?

Anyhow, Can you please help in understanding the meaning of this line?

+2

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

+1

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?

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

0

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

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

0

@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

+1

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

0

@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

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

0

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.

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.

0

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?

0

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

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

0

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?

0

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 !

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

0

@rahul

CSL can take infinite string

even CFL can take infinite string

So, why not recursive can take?

Finite string only for regular language

CSL can take infinite string

even CFL can take infinite string

So, why not recursive can take?

Finite string only for regular language

0

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?

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?

0

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.

+34 votes

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.

0

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

+1

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.

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

+1

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

+7 votes

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 *

–5 votes

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

0

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^{n}1^{n}} . L includes L1 but other strings also that makes L regular.

0

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

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.

0

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

0

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

+7

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

52,345 questions

60,513 answers

201,930 comments

95,354 users