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

[PDF] Solutions to the Final Exam - Washington

Show that every infinite Turing-recognizable language has an infinite decidable subset (Hint: Use the result in (a) and the result you know regarding Turing-

[PDF] Theory of Computation

(in NP) To show L is in NP, we need to show the existence of a TM M context- free languages is decidable, A is therefore recursive (6) (10 pts) Prove that every infinite Turing-recognizable language has an infinite Turing-decidable subset generates an infinite subset of the given r e language in lexicographical order

[PDF] Answers to the CSCE 551 Final Exam, April 30, 2008

30 avr 2008 · [This proves that every infinite Turing recognizable set has an infinite decidable subset ] Answer: Let L be the language enumerated by E If E prints a string longer than w, then reject” Since E enumerates an infinite language (by assumption), it must print strings that are arbitrarily long

[PDF] CSE 105 Homework 6 Due: Tuesday November 15 - UCSD CSE

15 nov 2016 · (10 points) Show that every infinite Turing-recognizable language has an infinite decidable subset (Sipser 3 19) 5 (10 points) Explain why the 

[PDF] Solutions for Problem Set 7

Solution: Let L be an infinite recursively enumerable language Since L is recursively an infinite, decidable subset of L Observe that, by construction, any string output by M1 is in L (as it must have been first output by M which tions, prove that Inf is not recursively enumerable (i e , Turing recognizable) Hint: Reduce a 

Sipser_2006_Second_Edition_Problemspdf

5 1 Undecidable Problems from Language Theory 188 Theory also is relevant to you because it shows you a new, simpler, and more *3 19 Show that every infinite Turing-recognizable language has an infinite decidable subset

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

Answer: A CFG is in Chomsky normal form if each of its rules has one of 3 forms: A → BC, Answer: A language whose complement is Turing-recognizable First show C ∈ NP by giving a deterministic polynomial-time verifier for C ( Alterna- Let L1,L2,L3, be an infinite sequence of regular languages, each of which is 

[PDF] CS660 Homework 1 - Department of Computer Science at the

8 avr 2018 · Solve as many of the problems as you can; please explain / prove all infinite Turing-recognizable language has an infinite decidable subset

[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

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