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