Recursive language problem... AGRE '97

**grabanca** · 10-23-2007, 10:10 PM

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
*

**taro_curly** · 10-24-2007, 04:07 AM

I think the answer is

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

**gttts23** · 10-24-2007, 06:24 AM

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.

**taro_curly** · 10-24-2007, 06:59 AM

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

**ethanph** · 10-25-2007, 04:29 PM

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

**R0jkumar** · 10-25-2007, 08:21 PM

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.

**grabanca** · 10-27-2007, 01:14 AM

I agree. I got it wrong first but it makes total sense. Thanks R0jkumar and Gttts23.

**endlessdream** · 10-28-2007, 06:20 AM

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.