Class Note for C SC 473 at UA
Popular in Course
Popular in Department
This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 23 views.
Reviews for Class Note for C SC 473 at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CSC 473 Automata Grammars amp Languages Lecture 06 Decidability and Undecidability c sc m Amman lt3me 4 Languages 1132008 Automata Grammars and Languages ADFA SAM I A is a DFA and we LA decidable anguage Pf A decider for the language is M On input ltAwgt Simulate A on w If the simulation reaches an accept state halt and accept If it ends jams in a nonaccept state halt and rejectquot C so on Autumn39s Gamma um Decidable Problems for Regular Languages Theorem 41 MembershipAcceptance Prob for DFAs ANFA ltNw l N is anNFA and we LN decidable language Pf A decider for the language is M On input ltNwgt Use the RabinScott algorithm to convertN to DFA A Run the Theorem 41 algorithm with input ltAwgt If that algorithm accepts then accept otherwise rejectquot C so on Autumn39s Gamma um Decidable Regular Langs cont d Theorem 42 MembershipAcceptance Prob for NFAs Lecture 06 CSC 473 Automata Grammars amp Languages 1132008 Decidable Regular Langs cont d Theorem 43 Membership Prob for RegEx39s AREX R w R is a regular expression and we LR is a decidable language Pf Use the algorithm to convert R to an equivalent NFA N and use the algorithm of Theorem 42 with input ltNwgt c sconAmnmu swabMs Decidable Regular Langs cont d Theorem 44 Emptiness Problem for DFAs EDFA ltA l A is a DFA and LA Q is a decidable language Pf A decider for the language is T On input ltAgt Settle repeatl M ltS S PM Ulq3d317 M5paql until S M if F m M Q accept otherwise rejectquot c sconAmnmu swabMs 5 Decidable Regular Langs cont d Theorem 45 Equivalence Problem for DFAs EQW 143 I AB are DFA and LA 43 is a decidable language Pf Observe that LA LB ltgt LA 6L3 Lhere LA 6 LB LA n LB U LA t LB Because of closure properties there is an algorithm to construct a DFA C from A B that accepts LA LB Use Theorem 44 with ltCgt to test whether LC Q If that algorithm accepts then accept otherwise reject c sconAmnmu swabMs 5 Lecture 06 2 CSC 473 Automata Grammars amp Languages Decidable Problems for CFLs Theorem 47 MembershipAcceptance Prob for CFGs Am GwgtIGisaCFG andwe LG isa decidable language Pf Chomsky Normal Form parse trees look like A A 2n 71 A 39s A A A A A A A A a A A i l l l l A a a a a a A A Pure Binary Tree Wn leaves a AA has n71 internal nodes i Add n terminating rules or a a a parse tree c gummy Qmemws n terminals 7 1132008 Decidable Problems CFLs cont d S On input ltGwgt ConvertG to CNF If lwlgt0 try all derivations with lelrl steps If w0 try the 1 step derivation S G g If anyderivation generates w accept else rejectquot Corollary Text Theorem 49 Every CFL is a decidable language Pf LetA be a CFL We want a decider for it Let G be a CFG generating A On input w run the TM S above on ltGwgt to accept or reject w c sconAmnmu swam 5 Decidable CFLs cont d Theorem 48 Emptiness Problem for CFGs ECFG 0 I G is aCFG and LG Q is a decidable language Pf A variable A in a CFG is produc ve or co reachable iff Ewe 239 A 3 w So LG Q iff the start variable S is productive See Homework 4 Problem 2 for an algorithm to decide whether a variable is productive All above problems also decidable for PDAs just convert to CFGs What about the Equivalence Problem for CFGs EQGG GHI GH are CFGs and LG LH We will show later that this problem is UNdecidable c sconAmnmu swam 9 Lecture 06 CSC 473 Automata Grammars amp Languages 1132008 The Halting Problem Although the following anguageisTMrecognizable we will show hm decidable AW MwgtIM is aTM andwe LM This is called the Membership Problem for TMs and by some authors the Halting Problem for TMs given a TM M and string w does M accept w Why called Halting Problemquot Given a TM M can always alter it to an equivalentTM M such that M halts on w iffM accepts w iffM accepts w Pf For each undefined transition 5qa in M M will transition to a state qtuuy and loop forever also 11mm goes to the same loop state Thus acceptance can be made synonymous with halting C so An Autumn smut Laws The Halting Problem cont d Thm AW MwIM isaTM and we LM is Turingrecognizable Pf Let Ubea UTM Arecognizer for ATM is R ye ye ltMwgt U no no ltMwgtE LR aMwe LU c we LM aMwe ATM El C so An Autumn smut Laws The Halting Problem cont d Thm AW MwIM isaTM and we LM is undecidable Pf Proof by contradiction Assume that ATM is decidable Then it has a decider call itH Hbehaves as follows Reefer If M accept w ltMwgt H reject If Mdoe not accept w Construct a TM D that calls Has a subroutine On input M D runs Hon M M That is Ddetermines ifM accepts or rejects its own description as input If M accepts M then D rejects lfM rejects M then D accepts Here is the picture of how D behaves C so An Autumn smut Laws Lecture 06 4 CSC 473 Automata Grammars amp Languages 1132008 The Halting Problem cont d zf M cceptsltMgtj W M M ccept gyms not mm M H reject lfMdoesnot V313 acceptltMgtj If M accepts ltMgtj ltMgtE LDltgtltMELM What happens if we run D on its own description D Set ltMgt D in the above Then ltDgtE LD ltgt ltDE LD This contradiction shows that decider Hcannot exist c SC on Autumn awe Laws Diagonalization Why called D computes the opposite of the diagonal entries DMl accept ltgt MlMl reject TMs a M2 M3 D M2ltMt M3Mt s E S S es utpmua is DD accept or reject DD accept ltgt DD reject c SC on Autumn awe Laws Decidable vs Recognizable Sets Basics Theorem L decidable 2 L decidable Proof If L is decidable it has a decider M The decider halts for every input in either the accepting halt stjte qmm or in the rejecting halt state 41mm Construct M from M as follows make the accepting halt state the rejecting state and the rejecting halt state the accepting state Then we LMcgtwe LM thatis LMLMt c SC on Autumn awe Laws Lecture 06 CSC 473 Automata Grammars amp Languages 1132008 Decidable vs Recognizable Basics Cont Theorem 422 L is decidable both L amp Z are Turing recognizable Proof 2 Previous theorem Suppose both are recognizable Let M be recognizers for L Construct M to simulate alternate steps i each recognizer accept M Ema accept w 7 mm M WEE reject Given w it is eventually accepted by one or the other so M must halt and either accept or reject it is a decider c 5cm Autumn swam 5 A Non TM Recognizable Set Corollary 423 R the complement of AM is not Turingrecognizable Pf By contradiction We know that AM is Turing recognizable Suppose R is Turingrecognizable By Theorem 422 it follows that Arm is decidable Since we know that AM is not decidable by Theorem 411 this contradiction establishes the result NoteiNhatdoes R look like ATM MwIM is a TMand we LMu J where J 01 011 which are all the junk strings that cannotbe of e form lt Codedmachine coded input gt Note that is a regular language C so on Autumn 6mg Laws Lecture 06 6
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'