# Theory of comp questions

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

1. ### mrburnerRon Paul 2008

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

[/size]

2. ### mrburnerRon Paul 2008

Joined:
May 9, 2001
Messages:
7,448
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. ### StuffGuest

2 words: kill yourself

4. ### mrburnerRon Paul 2008

Joined:
May 9, 2001
Messages:
7,448
0
Location:
Phoenix
but the semester is so close to an end

5. ### WERUreoImua!

Joined:
Oct 15, 2003
Messages:
566
0
Location:
Daytona Beach, Florida
What course is that for?

6. ### mrburnerRon Paul 2008

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

any ideas?

7. ### CyberBulletsI reach to the sky, and call out your name. If I c

Joined:
Nov 13, 2001
Messages:
11,865
0
Location:
contact me i can help with some of them. im baked right now! descrete math is ugly.

8. ### mrburnerRon Paul 2008

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

9. ### Achance007Active Member

Joined:
Oct 12, 2000
Messages:
16,128
4
Location:
New Castle, DE

Joined:
May 9, 2001
Messages:
7,448