CSC 427: Theory of Computation

my wechat：Yooo932851

Don't hesitate to contact me

Final

• There are 7 problems each worth 6 points and 1 extra credit problem worth 3 points.

• As an important protocol for today’s test, please turn your cameras on.

• While situations differ, every student is responsible for ensuring the integrity of the test, and must take all reasonable steps in support of ensuring the integrity.

• No notes, no collaboration. Please help the evaluation of partial credit by showing your work towards the solution. Do not be overly concerned with the challenge problems. Do your own work.

• Please sign the cover page so show agreement with these directions.

1. Reduce the following SAT instance to a 3SAT instance.

¬ (a ∧ b ∧ c ∧ d)∨ ¬(a ∨ (b ∧ c))

2. Give a Turing Machine that accepts the language of strings over{$, 0, 1} of strings that begin with a $ and are followed by an equal number 0’s and 1’s.

You may assume that the only characters in the string before the first blank is the leading $ then only 0’s and 1’s.

3. Put a ( X ) the box thatmost precisely describes the language.

The languages are,

ACF G ={ hG, wi | G is a CFG that generates stringw }

ADF A ={ hB, wi | B is a DFA that accepts input stringw }

AREX ={ hR, wi | R is a regular expression that generates stringw }

ATM ={ hM, wi | M is a TM andM acceptsw }

EQDF A ={ hA, Bi | A andB are DFAs andL(A) =L(B)}

EQTM ={ hM1, M2i | M1, M2 are TMs andL(M1) =L(M2)}

HALT TM ={ hM, wi | M is a TM andM halts on inputw }

REGULARTM ={ hMi | M is a TM andL(M) is a regular language}

For a languageX the languagecoX is the language of the complement set ofX.

4. Thek–clique problem is given a graph with vertex setV of sizen and edge setE of sizem, is there a subsetK of the vertex setV , such thatK is of sizek andK is a clique, that is, every pair of vertices inK are connected by an edge.

(a) Give an algorithm to solve the problem. Analyze the the algorithm runtime.

(b) It is likely your algorithm is not polynomial time. Is there a polynomial time algorithm for this problem?

5. (a) Show that P is closed under union, concatenation and comple ment.

(b)Extra Credit Problem: Show that P is closed by star.

6. Consider an polynomial in one variable with integer coefficients,

The notation for any such polynomial isp ∈ Z[x]. The languageR is the set of such polynomials that have an integer root,

(a) Give a P-time verifier for the setR.

(b) Give a decider for the setR. (Do not be concerned with runtime, except it must always decide in finite time.)

7. Show that,

CF LTM ={ hMi | M is a TM andL(M) is a context free language}

is undecidable.