# Thread: Recursive language problem... AGRE '97

1. Good post? |

## Recursive language problem... AGRE '97

Anyone wants to have a shot at this?

If L \subseteq {0,1}* is not recursive then which
of the following are true:
I. L' is not recursive
II. L is contained in a recursive set
III. L is infinite

A. I B. III C. I,III D. I,II,III
*

2. Good post? |

B) III only

Since L is not recursive, L' may be recursive, so I is not true

Since L is not recursive, it is not contained in a recursive set, so II is also not true

3. Good post? |
The correct answer is D) I, II and III

I is correct, because if L' was recursive then given a TM for L' all we need to do is to negate the answer and get a TM for L.

II is correct, because L is contained in {0,1}* which is a recursive set.

III is also correct because all finite languages are decidable.

G.

4. Good post? |
@gttts23

Your reasoning is any day better than the b****** that I came up with.
Thanks for that. Looks like I will have to work a lot harder on Theory.

5. Good post? |
i think the correct answer is C
L is recursive <=> L' is also recursive, so the is
L is not recursive <=> L' is also not recursive

so I. is correct

for II, i think it should be L contain a recursive set

6. Good post? |
Correct answer is (D) as gttts23 mentioned. The language (0
+1)* is recursive and hence contains every language of 0's and 1's . So, II holds as well.

7. Good post? |
I agree. I got it wrong first but it makes total sense. Thanks R0jkumar and Gttts23.

8. Good post? |
Hi gtts...,

Can we explain I in this way... if L' were recursive, then L must be recursive (due to closure property). Since L is not recursive, so L' is not recursive as well. So I is correct.

regarding II, what exactly means by "recursive set". From wikipedia "In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A set which is not computable is called noncomputable or undecidable.".

Would you por favor, el seņor distinguish the meaning of 'recursive language' and 'recursive set'? L is not recursive, then how it bovine mastication be in 'recursive set'?

regarding III, can you define what is finite language? Does it ask about finiteness of a language, or does it mean 'finite lanuage' which is defined in wikipedia as "A specific subset within the class of regular languages is the finite languages - those containing only a finite number of words. These are obviously regular as one can create a regular expression that is the union of every word in the language, and thus are regular."

Do you've good links on finiteness checking/properties of a language?

Sorry to disappoint asking too many basic concepts of automata theory!

Originally Posted by gttts23
The correct answer is D) I, II and III

I is correct, because if L' was recursive then given a TM for L' all we need to do is to negate the answer and get a TM for L.

II is correct, because L is contained in {0,1}* which is a recursive set.

III is also correct because all finite languages are decidable.

G.

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

SEO by vBSEO ©2010, Crawlability, Inc.