[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. Answer:SupposeAis a language defined over alphabet Σ1, andBis a language defined over alphabet Σ 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)) 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. Answer:SupposeAis a language defined over alphabet Σ1, andBis a language defined over alphabet Σ 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 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 A1A 2A 3A4 A 5 B NP C AtoBin polynomial time becauseBis NP-Complete, and then we can reduceBtoCin polynomial time, so the entire reduction ofAtoCtakes polynomial time. xvii. NP-hard (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? 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? 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.

Type DEC. It is Turing-decidable, but not context-free. For each of the following languages, specify which type it is. Also, follow these instructions: 4 •If a languageLis of Type REG, give a regular expressionanda DFA (5-tuple) forL. •If a languageLis of Type CFL, give a context-free grammar (4-tuple)anda PDA (6-tuple) for

L.Also, prove thatLis not regular.

•If a languageLis of Type DEC, give a description of a Turing machine that decidesL.Also, prove thatLis not context-free. (a)A={w?Σ?|w= reverse(w) and the length ofwis divisible by 4}, where Σ ={0,1}.

Circle one type: REG CFL DEC

Answer:Ais of type CFL. A CFGG= (V,Σ,R,S) forAhasV={S}, Σ ={0,1}, starting variableS, and rulesR={S→00S00|01S10|10S01|11S11|ε}. A PDA forAis as follows: q1q2 q3 q4 q5 q6ε, ε→$

0, ε→0

1, ε→10, ε→0

1, ε→1

0,0→ε

1,1→ε0,0→ε

1,1→ε

The above PDA has 6-tuple (Q,Σ,Γ,δ,q1,F), withQ={q1,q2,...,q6}, Σ ={0,1}, Γ =

{0,1,$}, starting stateq1,F={q1,q6}, and transition functionδ:Q×Σε×Γε→ P(Q×Γε)

defined by

Input:01ε

Stack:01$ε01$ε01$ε

q1{(q2,$)} q2{(q3,0)}{(q3,1)}{(q4,ε)} q3{(q2,0)}{(q2,1)} q4{(q5,ε)}{(q5,ε)}{(q6,ε)} q5{(q4,ε)}{(q4,ε)} q6

Blank entries are∅.

We now prove thatAis not regular by contradiction. Suppose thatAis regular. Letp≥1 be the pumping length of the pumping lemma (Theorem 1.I). Consider strings= 0p12p0p?A, and note that|s|= 4p > p, so the conclusions of the pumping lemma must hold. Thus, we can Because all of the firstpsymbols ofsare 0s, (3) implies thatxandymust only consist of 0s. Also,zmust consist of the rest of the 0s at the beginning, followed by 12p0p. Hence, we can write x= 0j,y= 0k,z= 0m12p0p, wherej+k+m=pbecauses= 0p12p0p=xyz= 0j0k0m12p0p. Moreover, (2) implies thatk >0. Finally, (1) states thatxyyzmust belong toA. However, xyyz= 0j0k0k0m12p0p= 0p+k12p0p becausej+k+m=p. But,k >0 implies reverse(xyyz)?=xyyz, which meansxyyz??A, which contradicts (1). Therefore,Ais a nonregular language. 5 (b)B={bnanbn|n≥0}.

Circle one type: REG CFL DEC

Answer:Bis of type DEC. Below is a description of a Turing machine thatdecidesB.

M= "On input stringw? {a,b}?:

1.Scan the input from left to right to make sure that

it is a member ofb?a?b?, andrejectif it isn"t.

2.Return tape head to left-hand end of tape.

3.Repeat the following until there are no morebs left on the tape.

4.Replace the leftmostbwithx.

5.Scan right until anaoccurs. If there are noa"s,reject.

6.Replace the leftmostawithx.

7.Scan right until aboccurs. If there are nob"s,reject.

8.Replace the leftmostb(after thea"s) withx.

9.Return tape head to left-hand end of tape, and go to stage 3.

10.If the tape contains anya"s,reject. Otherwise,accept."

We now prove thatBis not context-free by contradiction. Suppose thatBis context-free. Let pbe the pumping length of the pumping lemma for CFLs (Theorem 2.D), and consider string s=bpapbp?B. Note that|s|= 3p > p, so the pumping lemma will hold. Thus, we can split consider all of the possible choices forvandy: •Suppose stringsvandyare uniform (e.g.,v=bjfor somej≥0, andy=akfor some k≥0). Then|vy| ≥1 implies thatv?=εory?=ε(or both), souv2xy2zwon"t have the correct number ofb"s at the beginning,a"s in the middle, andb"s at the end. Hence, uv

2xy2z??B.

•Now suppose stringsvandyare not both uniform. Thenuv2xy2zwill not have the form b···ba···ab···b. Hence,uv2xy2z??B. Thus, there are no options forvandysuch thatuvixyiz?Bfor alli≥0. This is a contradiction, soBis not a CFL. (c)C={w?Σ?|na(w) mod 4 = 1}, where Σ ={a,b}andna(w) is the number ofa"s in string w. For example,na(babaabb) = 3. Also, recalljmodkreturns the remainder after dividingj byk, e.g., 3 mod 4 = 3, and 9 mod 4 = 1.

Circle one type: REG CFL DEC

Answer:Cis of type REG. A regular expression forCis (b?ab?ab?ab?ab?)?b?ab?, and a DFA forCis below: 6 q1q2 q3q4 a b a b a b a b The above DFA has 5-tuple (Q,Σ,δ,q1,F), withQ={q1,q2,q3,q4}, Σ ={a,b},q1as the starting state,F={q2}, and transition functionδ:Q×Σ→Qdefined by a b q1q2q1 q 2 q3q2 q 3 q4q3 q 4 q1q4 (d)D={bnanbkck|n≥0, k≥0}. [Hint: Recall that the class of context-free languages is closed under concatenation.]

Circle one type: REG CFL DEC

Answer:Dis of type CFL. A CFGG= (V,Σ,R,S) forDhasV={S,X,Y}, Σ ={a,b,c},

Sas the starting variable, and rulesR:

S→XY

X→bXa|ε

Y→bY c|ε

A PDA forDis below:

q1q2q3q4q5q6ε, ε→$ε, ε→ε b, ε→ba, b→ε b, ε→b c, b→ε We formally express the PDA as a 6-tuple (Q,Σ,Γ,δ,q1,F), whereQ={q1,q2,...,q6}, Σ = {a,b,c}, Γ ={b,$}(use $ to mark bottom of stack),q1is the start state,F={q6}, and the transition functionδ:Q×Σε×Γε→ P(Q×Γε) is defined by 7

Input:abcε

Stack:b$εb$εb$εb$ε

q1{(q2,$)} q2{(q2,b)}{(q3,ε)} q3{(q3,ε)}{(q4,$)} q4{(q4,b)}{(q5,ε)} q5{(q5,ε)}{(q6,ε)} q6

Blank entries are∅.

An important point to note about the above PDA is that the transition fromq3toq4pops and pushes $. It is important to pop$to make sure that the number ofa"s matches the number of b"s in the beginning. We need to push $to mark the bottom of the stack again for the second part of the string ofb"s andc"s. We now prove thatDis not regular by contradiction. Suppose thatDis regular. Letp≥1 be the pumping length of the pumping lemma (Theorem 1.I). Consider strings=bpapbpcp?D, and note that|s|= 4p > p, so the conclusions of the pumping lemma must hold. Thus, we can the firstpsymbols ofsareb"s, (3) implies thatxandymust only consist ofb"s. Also,zmust consist of the rest of theb"s at the beginning, followed byapbpcp. Hence, we can writex=bj, y=bk,z=bmapbpcp, wherej+k+m=pbecauses=bpapbpcp=xyz=bjbkbmapbpcp. Moreover, (2) implies thatk >0. Finally, (1) states thatxyyzmust belong toD. However, xyyz=bjbkbkbmapbpcp=bp+kapbpcp becausej+k+m=p. Alsok >0, soxyyz??D, which contradicts (1). Therefore,Dis a nonregular language.

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

Type DEC. It is Turing-decidable.

Type TMR. It is Turing-recognizable, but not decidable.

Type NTR. It is not Turing-recognizable.

For each of the following languages, specify which type it is. Also, follow these instructions: •If a languageLis of Type DEC, give a description of a Turing machine that decidesL. •If a languageLis of Type TMR, give a description of a Turing machine that recognizesL.

Also, prove thatLis not decidable.

•If a languageLis of Type NTR, give a proof that it is not Turing-recognizable. In each part below, if you need to prove that the given languageLis decidable, undecidable, or not Turing-recognizable, you must give an explicit proof of this; i.e., do not just cite a theorem that establishes this without a proof. However, if in your proof you need to show another languageL? has a particular property and there is a theorem that establishes this, then you may simply cite the theorem forL?without proof. (a)EQTM={?M1,M2? |M1,M2are TMs withL(M1) =L(M2)}. [Hint: show

Circle one type: DEC TMR NTR

Answer:EQTMis of type NTR (see Theorem 5.K). We prove this by showing and applying Corollary 5.I. Define the reducing functionf(?M,w?) =?M1,M2?, where 8 •M1= "rejecton all inputs." •M2= "On inputx:

1. Ignore inputx, and runMonw.

2. IfMacceptsw,accept;

IfMrejectsw,reject."

Note thatL(M1) =∅. For the language of TMM2,

•ifMacceptsw(i.e.,?M,w? ??ATM), thenL(M2) = Σ?; •ifMdoes not acceptw(i.e.,?M,w? ?ATM), thenL(M2) =∅.

Thus, if?M,w?is a YES instance for

ATM(i.e.,?M,w? ?ATM, soMdoes not acceptw), then

L(M1) =∅andL(M2) =∅, which are the same, implying thatf(?M,w?) =?M1,M2? ?EQTM is a YES instance forEQTM. Also, if?M,w?is a NO instance for

ATM(i.e.,?M,w? ??ATM,

soMacceptsw), thenL(M1) =∅andL(M2) = Σ?, which are not the same, implying that f(?M,w?) =?M1,M2? ??EQTMis a NO instance forEQTM. Hence, we see that?M,w? ? ATM ??f(?M,w?) =?M1,M2? ?EQTM, so (Corollary 4.M), soEQTMis not TM-recognizable by Corollary 5.I. (b)HALTTM={?M,w? |Mis a TM that halts on inputw}. [Hint: modify the universal TM to show thatHALTTMis Turing-recognizable.]

Circle one type: DEC TMR NTR

Answer:HALTTMis of type TMR (see Theorem 5.A). The following Turing machine recog- nizesHALTTM:

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

1.RunMonw.

2.IfMhalts onw,accept."

We now prove thatHALTTMis undecidable, which is Theorem 5.A. Suppose there exists aTM Rthat decidesHALTTM. Then we could useRto develop a TMSto decideATMby modifying the universal TM to first useRto see if it"s safe to runMonw.quotesdbs_dbs22.pdfusesText_28

[PDF] all font types list

[PDF] all fonts family css

[PDF] all fonts name list

[PDF] all fonts supported in html

[PDF] all fonts that can be used in html

[PDF] all formula of solution chapter

[PDF] all formulas of chapter 2 chemistry class 11

[PDF] all formulas of chemical kinetics class 12

[PDF] all formulas of electrochemistry

[PDF] all formulas of electrochemistry class 12

[PDF] all formulas of solutions class 12 chemistry

[PDF] all formulas of statistics class 10th

[PDF] all formulas of statistics class 11

[PDF] all formulas of statistics class 11 economics

[PDF] all formulas of statistics class 11 maths