retagged by
15,400 views
57 votes
57 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?

  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
retagged by

4 Answers

Best answer
136 votes
136 votes

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$. 
edited by
58 votes
58 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.

9 votes
9 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 

edited by
–5 votes
–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".
Answer:

Related questions