Publish on 03rd November 2019
Category: Birds
0

CSE 105theory of computation

Fall 2019https://cseweb.ucsd.edu/classes/fa19/cse105-a/

Today's learning goalsSipser Ch 4.1

Explain what it means for a problem to be decidable.Justify the use of encoding.Give examples of decidable problems.Use counting arguments to prove the existence of unrecognizable (undecidable) languages.

At start of CSE 105…

Pick a model of computationStudy what problems it can solveProve its limits

Classification: is input of type A or not?Decision problem{ w | w is of type A}PRIME = { 2, 3, 5, 7, … }SORTED = { <1,3>, <-1, 8, 17> …}Decision problems are coded by sets of strings

Encoding input for TMsSipser p. 159

By definition, TM inputs arestringsTo define TM M:"On input w …....…

For inputs that aren't strings,we have toencode the object(represent it as a string) first

Notation:<O>is thestringthat represents(encodes)the object O<O1, …, On> is thesinglestring that represents the tuple of objects O1, …, On

Encoding inputs

Payoff: problems we care about can be reframed as languages of stringse.g. "Recognize whether a string is a palindrome."{ w | w in {0,1}* and w = wR}e.g. "Check whether a string is accepted by a DFA."{ <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) }e.g. "Check whether the language of a PDA is infinite."{ <A> | A is a PDA and L(A) is infinite}

Encoding inputs

Payoff: problems we care about can be reframed as languages of stringse.g. "Recognize whether a string is a palindrome."{ w | w in {0,1}* and w = wR}This set is regular and decidable.This set is regular and not decidableThis set is nonregular and decidableThis set is nonregular and not decidable.None of the above

Computational problems

A computational problem isdecidableiff the language encoding the problem instances is decidable

Computational problems

Sample computational problems and their encodings:ADFA"Check whether a string is accepted by a DFA."{ <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) }EDFA"Check whether the language of a DFA is empty."{ <A> | A is a DFA over Σ, L(A) is empty }EQDFA"Check whether the languages of two DFA are equal."{ <A, B> | A and B are DFA over Σ, L(A) = L(B)}..

Computational problems

Sample computational problems and their encodings:ADFA"Check whether a string is accepted by a DFA."{ <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) }EDFA"Check whether the language of a DFA is empty."{ <A> | A is a DFA over Σ, L(A) is empty }EQDFA"Check whether the languages of two DFA are equal."{ <A, B> | A and B are DFA over Σ, L(A) = L(B)}FACT: all of these problems are decidable!

Proving decidability

Claim:ADFAis decidableProof:WTS that { <B,w> | B is a DFA over Σ, w in Σ*, and w is in L(B) } is decidable.Step 1: constructionHow would you check if w is in L(B)?

Proving decidability

<A, 1> is not in ADFA<A, 01> is not in ADFA<B, 1> is not in ADFA<B, 01> is not in ADFAMore than one of the above

A

B

Proving decidability

Define TM M1by: M1= "On input <B,w>Check whether input is a valid encoding of a DFA and input string for that DFA. If not, reject.Simulate running B on w(by keeping track of states in B, transition function of B, etc.)When the simulation ends, by finishing to process all of w, check current state of B: if it is final,accept; if it is not, reject."

Proving decidability

Step 1: constructionDefine TM M1by M1= "On input <B,w>Check input is a valid encoding of a DFA and input string for that DFA. If not, reject.Simulate running B on w(by keeping track of states in B, transition function of B, etc.)When the simulation ends, by finishing to process all of w, check current state of B: if it is final,accept; if it is not, reject."Step 2: correctness proofWTS(1)L(M1) = ADFAand(2)M1is a decider.

Proving decidability

Claim:EDFAis decidableProof:WTS that { <A> | A is a DFA over Σ, L(A) is empty } is decidable.

Proving decidability

Claim:EDFAis decidableProof:WTS that { <A> | A is a DFA over Σ, L(A) is empty } is decidable.e.g.< > is in EDFA; < > is not in EDFATM deciding EDFAshould accept and should reject

Proving decidability

Claim:EDFAis decidableProof:WTS that { <A> | A is a DFA over Σ, L(A) is empty } is decidable.Idea: give high-level descriptionStep 1: constructionWhat condition distinguishes between DFA that accept *some* string and those that don't accept *any*?

Proving decidability

Claim:EDFAis decidableProof:WTS that { <A> | A is a DFA over Σ, L(A) is empty } is decidable.Idea: give high-level descriptionStep 1: constructionWhat condition distinguishes between DFA that accept *some* string and those that don't accept *any*?

Proving decidability

Claim:EDFAis decidableProof:WTS that { <A> | A is a DFA over Σ, L(A) is empty } is decidable.Idea: give high-level descriptionStep 1: constructionDefine TM M2by: M2= "On input <A>:Check whether input is a valid encoding of a DFA; if not, reject.Mark the start state of A.Repeat until no new states get marked:Loop over states of A and mark any unmarked state that has anincomingedge from a marked state.If no final state of A is marked,accept; otherwise,reject.

Proving decidability

Step 1: constructionDefine TM M2by: M2= "On input <A>:Check whether input is a valid encoding of a DFA; if not, reject.Mark the state state of A.Repeat until no new states get marked:Loop over states of A and mark any unmarked state that has anincomingedge from a marked state.If no final state of A is marked,accept; otherwise,reject.Step 2: correctness proofWTS(1)L(M2) = EDFAand(2)M2is a decider.

Proving decidability

Claim:EQDFAis decidableProof:WTS that { <A, B> | A, B are DFA over Σ, L(A) = L(B) } is decidable.Idea: give high-level descriptionStep 1: constructionWill we be able to simulate A and B?What does set equality mean?Can we use our previous work?

Proving decidability

Claim:EQDFAis decidableProof:WTS that { <A, B> | A, B are DFA over Σ, L(A) = L(B) } is decidable.Idea: give high-level descriptionStep 1: constructionWill we be able to simulate A and B?What does set equality mean?Can we use our previous work?

Proving decidability

Claim:EQDFAis decidableProof:WTS that { <A, B> | A, B are DFA over Σ, L(A) = L(B) } is decidable.Idea: give high-level descriptionStep 1: constructionVery high-level:Build new DFA recognizing symmetric difference of L(A), L(B). Check if this set is empty.

Proving decidability

Claim:EQDFAis decidableProof:WTS that { <A, B> | A, B are DFA over Σ, L(A) = L(B) } is decidable.Idea: give high-level descriptionStep 1: constructionDefine TM M3by: M3= "On input <A,B>:Check whether input is valid encoding of pair of DFAs; if not, reject.Construct a new DFA, D, from A,Busing algorithms for complementing, taking unions of regular languagessuch that L(D) = symmetric difference of L(A) and L(B).Run machine M2on <D>.If it accepts, accept; if it rejects, reject."

Proving decidability

Step 1: constructionDefine TM M3by: M3= "On input <A,B>:Check whether input is valid encoding of pair of DFAs; if not, reject.Construct a new DFA, D, from A,Busing algorithms for complementing, taking unions of regular languagessuch that L(D) = symmetric difference of L(A) and L(B).Run machine M2on <D>.If it accepts, accept; if it rejects, reject."Step 2: correctness proofWTS(1)L(M3) = EQDFAand(2)M3is a decider.

TechniquesSipser 4.1

Subroutines: can use decision procedures of decidable problems as subroutines in other algorithmsADFAEDFAEQDFAConstructions: can use algorithms for constructions as subroutines in other algorithmsConverting DFA to DFA recognizing complement (or Kleene star).Converting two DFA/NFA to one recognizing union (or intersection, concatenation).Converting NFA to equivalent DFA.Converting regular expression to equivalent NFA.Converting DFA to equivalent regular expression.

Undecidable?

There are many ways to prove that a problemisdecidable.How do we find (and prove) that a problemis notdecidable?

0

Embed

Upload

CSE 105 Theory of Computation - cseweb.ucsd.edu