Couple of quick new theory of comp questions

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

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    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


    thanks in advance
     
  2. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix

Share This Page