[PDF] Practice Problems for Final Exam: Solutions CS 341: Foundations of

View - Download Practice Problems for Final Exam: Solutions CS 341: Foundations of

Previous PDF

Next PDF

Practice Problems for Final Exam: Solutions

CS 341: Foundations of Computer Science II

Prof. Marvin K. Nakayama

1. Short answers:

(a) Define the following terms and concepts: i. Union, intersection, set concatenation, Kleene-star, set subtraction, complement

Answer:Union:S?T={x|x?Sorx?T}

Intersection:S∩T={x|x?Sandx?T}

Concatenation:S◦T={xy|x?S,y?T}

Kleene-star:S?={w1w2···wk|k≥0,wi?S?i= 1,2,...,k}

Subtraction:S-T={x|x?S,x??T}

Complement:

S={x?Ω|x??S}= Ω-S, where Ω is the universe of all elements under consideration. ii. A setSis closed under an operationf Answer:Sis closed underfif applyingfto members ofSalways returns a member ofS. iii. Regular language

Answer:A regular language is defined by a DFA.

iv. Kleene"s theorem Answer:A language is regular if and only if it has a regular expression. v. Context-free language

Answer:A CFL is defined by a CFG.

vi. Chomsky normal form Answer:A CFG is in Chomsky normal form if each of its rules has one of 3 forms:A→BC, A→x, orS→ε, whereA,B,Care variables,BandCare not the start variable,xis a terminal, andSis the start variable. vii. Church-Turing Thesis Answer:The informal notion of algorithm corresponds exactly to a Turing machine that always halts (i.e., a decider). viii. Turing-decidable language Answer:A languageAthat is decided by a Turing machine; i.e., there is a Turing machine Msuch thatMhalts and accepts on any inputw?A, andMhalts and rejects on input inputw??A; i.e., looping cannot happen. ix. Turing-recognizable language Answer:A languageAthat is recognized by a Turing machine; i.e., there is a Turing machineMsuch thatMhalts and accepts on any inputw?A, andMrejects or loops on any inputw??A. x. co-Turing-recognizable language Answer:A language whose complement is Turing-recognizable. 1 xi. Countable and uncountable sets Answer:A setSis countable if it is finite or we can define a correspondence betweenSand the positive integers. In other words, we can create a list ofall the elements inSand each specific element will eventually appear in the list. An uncountable set is a set that is not countable. A common approach to prove a set is uncountable isby using a diagonalization argument. xii. LanguageAis mapping reducible to languageB,A≤mB Answer:SupposeAis a language defined over alphabet Σ1, andBis a language defined over alphabet Σ

2. ThenA≤mBmeans there is a computable functionf: Σ?1→Σ?2such

thatw?Aif and only iff(w)?B. Thus, ifA≤mB, we can determine if a stringw belongs toAby checking iff(w) belongs toB.

1Σ?

2 ABf f w?A??f(w)?B YES instance for problemA??YES instance for problemB xiii. Functionf(n) isO(g(n)) Answer:There exist constantscandn0such that|f(n)| ≤c·g(n) for alln≥n0. xiv. Classes P and NP Answer:P is the class of languages that can bedecidedby adeterministicTuring machine inpolynomial time. NP is the class of languages that can beverifiedin (de- terministic)polynomial time. Equivalently, NP is the class of languages that can be decidedby anondeterministicTuring machine inpolynomial time. xv. LanguageAis polynomial-time mapping reducible to languageB,A≤PB. Answer:SupposeAis a language defined over alphabet Σ1, andBis a language defined over alphabet Σ

2. ThenA≤PBmeans there is a polynomial-time computable function

f: Σ?1→Σ?2such thatw?Aif and only iff(w)?B. xvi. NP-complete Answer:LanguageBis NP-Complete ifB?NP, and for every languageA?NP, we have

A≤PB.

A1A 2A 3A4 A 5 B NP 2 The typical approach to proving a languageCis NP-Complete is as follows: •First showC?NP by giving a deterministic polynomial-time verifier forC. (Alterna- tively, we can showC?NP by giving a nondeterministic polynomial-time decider for C.) •Next show that a known NP-Complete languageBcan be reduced toCin polynomial time; i.e.,B≤PC. A1A 2A 3A4 A 5 B NP C Note that the second step implies thatA≤PCfor eachA?NP Because we can first reduce AtoBin polynomial time becauseBis NP-Complete, and then we can reduceBtoCin polynomial time, so the entire reduction ofAtoCtakes polynomial time. xvii. NP-hard Answer:LanguageBis NP-hard if for every languageA?NP, we haveA≤PB. (b) Give the transition functionsδ(i.e., specify the domains and ranges) of a DFA, NFA, PDA, Turing machine and nondeterministic Turing machine.

Answer:

•DFA,δ:Q×Σ→Q, whereQis the set of states and Σ is the alphabet. •NFA,δ:Q×Σε→ P(Q), where Σε= Σ? {ε}andP(Q) is the power set ofQ

•PDA,δ:Q×Σε×Γε→ P(Q×Γε), where Γ is the stack alphabet and Γε= Γ? {ε}.

•Turing machine,δ:Q×Γ→Q×Γ× {L,R}, where Γ is the tape alphabet,Lmeans move

tape head one cell left, andRmeans move tape head one cell right.

•Nondeterministic Turing machine,δ:Q×Γ→ P(Q×Γ× {L,R}), where Γ is the tape

alphabet,Lmeans move tape head one cell left, andRmeans move tape head one cell right. (c) Explain the "P vs. NP" problem. Answer:P is the class of languages that can be solved in polynomial time, and NP is the class of languages that can be verified in polynomial time. We know that P?NP. To see why, note that each TM is also an NTM, so deciding in deterministic polynomial time is a special case of deciding in nondeterministic polynomial time, making P?NP. But it is currently unknown if

P = NP or P?= NP.

2. Recall thatATM={?M,w? |Mis a TM that accepts stringw}.

(a) Prove thatATMis undecidable. You may not cite any theorems or corollariesin your proof. Overview of Proof:We use a proof by contradiction. SupposeATMis decided by some TM H, soHaccepts?M,w?if TMMacceptsw, andHrejects?M,w?if TMMdoesn"t acceptw.

H-→?M,w?

????accept, if?M,w? ?ATM reject, if?M,w? ??ATM 3

Define another TMDusingHas a subroutine.

HHD ?M,?M?? ????acceptreject-→?M? acceptreject SoDtakes as input any encoded TM?M?, then feeds?M,?M??as input intoH, and finally outputs the opposite of whatHoutputs. BecauseDis a TM, we can feed?D?as input intoD.

What happens when we runDwith input?D??

HHD ?D,?D?? ????acceptreject-→?D? acceptreject Note thatDaccepts?D?iffDdoesn"t accept?D?, which is impossible. Thus,ATMmust be undecidable. Complete Proof:Suppose there exists a TMHthat decidesATM. TMHtakes input?M,w?, whereMis a TM andwis a string. If TMMaccepts stringw, then?M,w? ?ATMandH accepts input?M,w?. If TMMdoes not accept stringw, then?M,w? ??ATMandHrejects input?M,w?. Consider the languageL={?M? |Mis a TM that does not accept?M?}. Now construct a TMDforLusing TMHas a subroutine:

D= "On input?M?, whereMis a TM:

1.RunHon input?M,?M??.

2.IfHaccepts,reject. IfHrejects,accept."

If we run TMDon input?D?, thenDaccepts?D?if and only ifDdoesn"t accept?D?. Because this is impossible, TMHmust not exist, soATMis undecidable. (b) Show thatATMis Turing-recognizable. Answer:The universal TMUrecognizesATM, whereUis defined as follows:

U= "On input?M,w?, whereMis a TM andwis a string:

1.RunMonw.

2.IfMacceptsw,accept; ifMrejectsw,reject."

Note thatUonly recognizesATMand does not decideATMBecause when we runMonw, there is the possibility thatMneither accepts nor rejectswbut rather loops onw.

3. Each of the languages below in parts (a), (b), (c), (d) is ofone of the following types:

Type REG. It is regular.

Type CFL. It is context-free, but not regular.

quotesdbs_dbs2.pdfusesText_2

[PDF] show that every tree with exactly two vertices of degree one is a path

[PDF] show that f is continuous on (?? ?)

[PDF] show that for each n 1 the language bn is regular

[PDF] show that if a and b are integers with a ? b mod n then f(a ? f(b mod n))

[PDF] show that if an and bn are convergent series of nonnegative numbers then ? anbn converges

[PDF] show that if f is integrable on [a

[PDF] show that if lim sn

[PDF] show that p ? q and p ? q are logically equivalent slader

[PDF] show that p ? q and p ? q ? p ? q are logically equivalent

[PDF] show that p(4 2) is equidistant

[PDF] show that p2 will leave a remainder 1

[PDF] show that the class of context free languages is closed under the regular operations

[PDF] show that the class of turing recognizable languages is closed under star

[PDF] show that the family of context free languages is not closed under difference

[PDF] show that the language l an n is a multiple of three but not a multiple of 5 is regular