# Couple of quick new theory of comp questions

Discussion in 'OT Technology' started by mrburner, Apr 4, 2004.

1. ### mrburnerRon Paul 2008

Joined:
May 9, 2001
Messages:
7,448
0
Location:
Phoenix
new homework assignment...got most of it done...couple i can't get and can't find any info about in my book/notes/online

so if anyone can help out at all, this set is due monday so any help today or tomorrow would be very much appreciated...if anyone could lead me in the right direction or anything, i would appreicate it...thanks

1. prove that the language that is the union of k countable sets is countable. your proof must take the form of either (i) and infinite-loop TM to enumerate the elements of the union of k countable sets, or (ii) a mathematical description of a correspondence between L and the natural numbers.

2. give a high level description of a 2-tape non-deterministic TM that decides the language L = {<w, v> | v is a substring of w and w, v €[imagine this symbol with only 1 line through the middle instead of 2] {0, 1} and w, v != epsilon}

3. explain why the RE languages are not closed under the complementation operation

4. Explain why the recursive languages are closed under complementation

Joined:
May 9, 2001
Messages:
7,448