Theory of comp questions

Discussion in 'OT Technology' started by mrburner, May 1, 2004.

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    I have a homework set that i have been working on for awhile here and there are a couple questions i had to skip over because i was totally clueless and couldn't find any info in the book or on google

    it may look semi long but there are really only 3 questions here...

    if anyone could help me out or point me in the right direction, it would be much appreciated...even if you only kinda know or might have a slight bit of input, it would be appreciated

    1. True or false with formal justification: The problem A belongs to the NP complexity class so an efficient algorithm for A exists

    2. L = {w[size=-1]∈Σ* | where each opening symbol, "[, <", has a matching closing symbol, "], >"} and Σ* = {[, <, a, >, ]}. The string []aa<a[a]> is an element of L while the string <<a<<[] is not.

    Classify the language L as tightly as possible using formal techniques.
    a) To show that a language is regular, construct a DFA or regular expression and you are done.

    b) To show that a language is CF, construct a PDA or CFG and then show that the language is not regular.

    c) To show that a language is Recursive, construct a deciding TM and then show that the language is not CF.

    d) To show that the language is RE construct an accepting TM and reduce the language to an undecidable language.

    e) To show that the language is co-RE reduce to a co-RE language.

    3. Given the sextuple of language classes, (R, CF, Recursive, RE, P, NP) then every language can be associated with a binary sextuple where symbol 1 denotes membership and symbol 0 denotes non-membership. For example, if the language were in the first calss and not in any others, it would be associated with (1, 0, 0, 0, 0, 0). State the binary sextuple associated with each of the following languages.

    a) L = {a, aa, ab}
    b) L = {w[/size][size=-1]∈{a, b}* | where |w| is odd and w contains exactly one b in the center of the word}
    c) L = {w[/size][size=-1]∈{a, b}* | where |w| is odd and w contains exactly one b}
    d) L = {The language of chess board configurations where white can win}
    e) L = {The language of graphs that have a tour where each vertex is visited exactly once}
    f) State three binary sextuplets that cannot exist and indicate where the contradiction occurs in each case



    once again, any help on any of these questions would be greatly appreciated

    thanks in advance
    [/size]
     
  2. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    here are 2 more that i am incredibly confused on

    4. Sue, a programmer, wishes to improve the efficiency of function call parameter passing in her program. In the existing code, objects are often passed by value to functions that do not modify these objects under any circumstances. To avoid the overhead of copying the objects when such functions are called, it would be preferable to pass the objects by reference. Sue decides to write an algorithm A that takes a description of a function f() as input and determines whether its arguments (currently passed by value) are modified during the execution of f. If an argument is not modified then it can safely be passed by reference without changing the semantics of the program. Assume f() may only access objects passed as arguments or to locally declared objects - no globals are allowed.

    a) Consider a restricted version of the problem where f() receives a single argument B and makes no function calls within the body of f(). Prove the decidability or undecidability of this problem.

    b) Consider the more general case of this problem where f() receives an arbitrary number of arguments and may call itself or other functions. Prove the decidability or undecidability of this problem.

    (now what i'm thinking is that part a is decidable and part b is not since in part a there are no function calls being made and the arguments cannot possibly change yet in part b we really have no idea as there are an abitrary number of arguments and the fact that it can call itself and other functions...since we have no idea whether or not the arguments are modified during execution, we have no idea whether or not this is decidable...whether or not i'm right or even close though, i have no idea)


    now here is the one that has had me scratching my head for over an hour...i couldn't have less of a clue on how to do this
    5. L = {111} be the language over {0, 1}* which contains only the string 111.
    a) Show that L can be accepted by a 5-state DFA
    b) Prove that L cannot be accepted by a 4-state DFA
     
  3. Stuff

    Stuff Guest

    2 words: kill yourself
     
  4. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    but the semester is so close to an end :(
     
  5. WERUreo

    WERUreo Imua!

    Joined:
    Oct 15, 2003
    Messages:
    566
    Likes Received:
    0
    Location:
    Daytona Beach, Florida
    What course is that for?
     
  6. mrburner

    mrburner Ron Paul 2008

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

    any ideas?
     
  7. CyberBullets

    CyberBullets I reach to the sky, and call out your name. If I c

    Joined:
    Nov 13, 2001
    Messages:
    11,865
    Likes Received:
    0
    Location:
    BC, Canada/Stockholm, Sweden
    contact me i can help with some of them. im baked right now! descrete math is ugly.
     
  8. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    anyone? please? i need to get this done tonight
     
  9. Achance007

    Achance007 Active Member

    Joined:
    Oct 12, 2000
    Messages:
    16,128
    Likes Received:
    4
    Location:
    New Castle, DE
  10. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    yeah notice how i said if anyone can point me in the right direction or help me out at all

    i'm not looking for someone to do my homework and i never said i was

    so unless you can help me with the questions at hand, please don't bother responding
     

Share This Page