[PDF] Tutorial 3 Exercise 3 (compulsory). Prove that

View - Download Tutorial 3

Previous PDF

Next PDF

COMPUTABILITY ANDCOMPLEXITYTUTORIAL3Tutorial 3

Exercise 1 (compulsory)

Consider the following claim:

Claim:IfLis a decidable language andL0L, thenL0is a decidable language too. Is this claim true? If yes, prove it. If not, give a counter-example.

Solution:

This claim is wrong. LetL= . This is surely a decidable language, however, any languageL0is now a subset ofL. Then any undecidable languageL0(and we know that undecidable languages exist - e.g. the

equality problem of CFG, or the acceptance problem of a TM) will satisfy the precondition of the claim

(being a subset ofL) but will break the conclusion asL0is not a decidable language.Exercise 2 (compulsory)

Consider the following problem:

"Does a given regular expressionRover =f0;1gdescribe a language, which contains at least one string starting with11and ending with0?" 1.

Express the problem as a language RU110.

2.

Pro vethat RU110is decidable.

Solution:

1. The problem has one input, the re gulare xpressionR, and should therefore be expressed as the language RU

110def=

fhRi jRis a reg. expr. overf0;1gand there isw2L(R)such thatw= 11u0for someu2 f0;1gg 2.

W epro vethat RU110is decidable by constructing a decider for it. This decider first converts a regular

expressionRto an NFA. Next, it converts the NFA to a DFA. Finally, we examine the DFA to see if there is a path from the start state to an accept state that begins with11and ends with0.

The complete algorithm is now as follows:

"On inputhRi: 1.

Con vertRto an NFAN.

2.

Con vertNto an DFAM.

3. Let s0denote the unique state ofMthat can be reached from the start state ofMby reading the string11. 4. Let TdenotethesetofallstatesfromwhichwecanreachanacceptstateofMbyreading a0. 5. Check if there is a path in Mfroms0to some state inT(can be done e.g. by depth-first search). 6. If there is such a path then accept, elsereject."1 COMPUTABILITY ANDCOMPLEXITYTUTORIAL3Exercise 3 (compulsory) Prove that the class of decidable languages is closed under union, concatenation and Kleene star.

Solution:

Closure under union. LetL1andL2be two decidable languages. By definition there are deciders M

1andM2such thatL(M1) =L1andL(M2) =L2. We construct the following 2-tape Turing

machineM: 1. "On input x: 2.

Cop yxon the second tape.

3.

On the first tape run M1onx.

4. If M1accepted thenMacceptselse continue with step 5. 5.

On the second tape run M2onx.

6.

If M2accepted thenMacceptselseMrejects."

NowMis surely a decider because bothM1andM2are deciders andL(M) =L1[L2. Any 2-tape decider is equivalent to some single tape decider. Hence we have a decider for the union ofL1and L 2. Closure under concatenation. LetL1andL2be two decidable languages. By definition there are decidersM1andM2such thatL(M1) =L1andL(M2) =L2. We construct the following nonde- terministic 3-tape Turing machineM: 1. "On input x: 2. Nondeterministically split the input string into tw opart sx=w1w2and copyw1on second tape andw2on the third tape. 3.

On the second tape run M1onw1.

4. If M1accepted then continue with step 5, elseMrejects. 5.

On the third tape run M2onw2.

6.

If M2accepted thenMacceptselseMrejects."

NowMis surely a nondeterministic decider because bothM1andM2are deciders andL(M) = L

1L2. Any 3-tape nondeterministic decider is equivalent to some single tape deterministic decider.

Hence we have a decider for the concatenation ofL1andL2. Closure under Kleene star. LetL1be a decidable language. By definition there is a deciderM1such thatL(M1) =L1. We construct the following nondeterministic 2-tape Turing machineM: 1. "On input x: 2. Nondeterministically select a nonempty left-most part of the input xwhich has not been read yet and copy it on the second tape 3.

On the second tape run M1on the present string.

4. If M1accepted and the whole inputxwas processed, thenMaccepts. IfM1accepted and some suffix ofxstill has to be processed then clean the second tape and continue with step 2.

IfM1rejected thenMrejects.

NowMis surely a nondeterministic decider becauseM1is a decider andL(M) =L1. Any 2-tape nondeterministic decider is equivalent to some single tape deterministic decider. Hence we have a decider for the Kleene star ofL1.2 COMPUTABILITY ANDCOMPLEXITYTUTORIAL3Exercise 4 (compulsory)

Prove that the class of recognizable languages is closed under intersection, concatenation and Kleene star.

Solution:

Closure under intersection. Notice that (unlike for union) there is no problem in running the machine

M

1first andM2second because they both have to accept (and hence terminate). This means that

the same construction as for the intersection of decidable languages presented in Lecture 3 will work

also for recognizable languages. Closure under concatenation and Kleene star. Again, try to go carefully through the proofs in the previous exercise and realize that the same constructions will work also for recognizable languages. Even if the for some splittings of the input stringxthe recognizers may now loop, if there exists a good splitting then the nondeterminism will simply find it.Exercise 5 (compulsory)

Consider the following two proofs that try to show that recognizable languages are closed under comple-

ment.

Proof 1:

LetLbe a recognizable language. By definition there is a Turing machineMsuch that

L(M) =L. Consider the following machineM0:

1.

On input x:

2.

Simulate Monx.

3. If Maccepted thenM0rejects. IfMrejected thenM0accepts. Now we can see thatL(M0) =L. HenceLis recognizable.

Proof 2:

LetLbe a recognizable language. By definition there is a Turing machineMsuch that

L(M) =L. Consider the following machineM0:

1.

On input x:

2.

Simulate Monx.

3. If Maccepted thenM0rejects. IfMrejected or looped onxthenM0accepts. Now we can see thatL(M0) =L. HenceLis recognizable.

As we already know, recognizable languages are not closed under complement and hence there must be an

error in both proofs. Locate the errors by underlining them and explain (e.g. by giving a counter example)

where is the problem.

Solution:

Proof 1:

LetLbe a recognizable language. By definition there is a Turing machineMsuch that

L(M) =L. Consider the following machineM0:

1.

On input x:

2.

Simulate Monx.

3 COMPUTABILITY ANDCOMPLEXITYTUTORIAL33.If Maccepted thenM0rejects. IfMrejected thenM0accepts. Now we can see thatL(M0) =L. HenceLis recognizable. The presented construction does not recognize the complement of the languageL. Consider a TMMover =fagwith three statesq0,qacceptandqrejectsuch that(q0;a) = (q0;a;R)and(q0;t) = (q0;a;R). On any given inputxthe machineMwill always loop (keep moving the head to the right) and hence L(M) =;. BecauseM0run onxwill first try to simulateMonx, it will never terminate either and hence L(M0) =;, which is surely not equal to the complement of the empty language.

Proof 2:

LetLbe a recognizable language. By definition there is a Turing machineMsuch that

L(M) =L. Consider the following machineM0:

1.

On input x:

2.

Simulate Monx.

3. If Maccepted thenM0rejects. IfMrejected or loopedonxthenM0accepts. Now we can see thatL(M0) =L. HenceLis recognizable. The problem here is that the machineM0has no way to verify whether the machineMonxloops or not. Hence conditions of the type "if a Turing machineMon an inputxloops then do something" cannot be a

part of any correct definition of a Turing machine because this test cannot be done algorithmically.Exercise 6 (optional and challenging)

Problem 4.10 on page 185.

4quotesdbs_dbs14.pdfusesText_20

[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

[PDF] show that x is a cauchy sequence

[PDF] show that x is a discrete random variable

[PDF] show that x is a markov chain

[PDF] show that x is a random variable

[PDF] show that [0

[PDF] show the mechanism of acid hydrolysis of ester

[PDF] show ? n 2 1 n log np converges if and only if p > 1

[PDF] shredded workout plan pdf

[PDF] shredding diet

[PDF] shredding workout plan

[PDF] shrm furlough

[PDF] shuttle paris

[PDF] si clauses french examples