THEORY OF COMPUTATION
THEORY OF COMPUTATION CIS 511
Popular in Course
Popular in Computer & Information Science
This 15 page Class Notes was uploaded by Jackson Will on Monday September 28, 2015. The Class Notes belongs to CIS 511 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/215418/cis-511-university-of-pennsylvania in Computer & Information Science at University of Pennsylvania.
Reviews for THEORY OF COMPUTATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/28/15
68 The Post Correspondence Problem The Post correspondence problem due to Emil Post is another undecid able problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable Let E be an alphabet with at least two letters An instance of the Post Correspondence problem for short7 PCP is given by two sequences U 1117 7um and V 11 mm of strings uhoi E 2 The problem is to nd whether there is a nite sequence 23917 7 with 23 E 17 7771 for j1o7 sothat uilui2 uip Wily 1 Equivalently7 an instance of the PCP is a sequence of pairs For example7 consider the following problem abab aaabbb aab ba ab aa ababaaa 7 bb 7 baab 7 baa 7 ba 7 a 39 There is a solution for the string 1234556 abab aaabbb aab ba ab ab aa ababaaa bb baab baa ba ba 1 We are beginning to suspect that this is a hard problem lndleedl7 it is undecidablel Theorem 681 Emil Post 1946 The Post correspondence problem is ahdeeldable provided that the alphabet E has at least two symbols There are several ways of proving Theorem 6817 but the strategy is more or less the same Reduce the halting problem to the PCP7 by encoding sequences of lD7s as partial solutions of the PCP For instance7 this can be done for RAM programs The rst step is to show that every RAM program can be simulated by a single register RAM program Then7 the halting problem for RAM programs with one register is reduced to the PCP using the fact that only four kinds of instructions are needed A proof along these lines was given by Dana Scott As an application7 we prove the following result Theorem 682 It is undecidable whether a contact free grammar is am biguous Proof We reduce the PCP to the ambiguity problem for CFG7S Given any instance U 1117um and V 1117vm of the PCP7 let 017 cm be m new symbols7 and consider the following languages LUui1 uipCip Ci1 l1 32537717 13739 31071021 LVUi1quot39UipCipquot Cill1 j m71 j 1071021h and LUV LUULv We can easily construct a CFG7 Gav generating LUy The productions are l The Post S SU S gt SV SU uiSUCi SU gt uici SV gt UiSVCi SV 150139 It is easily seen that the PCP for U7 V has a solution iff LU LV 7E Q iff G is ambiguous Remark As a corollary7 we also obtain the following result It is unde cidable for arbitrary context free grammars G1 and G2 whether LG1 LG2 U see also Theorem 692 69 Undecidable Properties of Languages Greibach s Theorem Recall that the computations of a Turing Machine M can be described in terms of instantaneous descriptions upav We can encode computations IDOhIDlh FIB halting in a proper ID as the language LM consisting all of strings w0wfw2w 39 39 w2kw klv or wowfw2w 39 39 w2k72w k71w2k7 where k 2 0 we is a starting 1D w F w for all 2 with 0 S 2 lt 2k 1 and 202k is proper halting ID in the rst case 0 S 2 lt 2k and 20 is proper halting ID in the second case The language LM turns out to be the intersection of two context free lan guages LR and L de ned as follows 1 The strings in L0 are of the form M w0w w2w 39 39 39w2kw k1 or R R R wow1 w2w3 39 39 w2k72w2k71w2k7 where LUgl39 h rum1 for all 239 2 07 and Lng is a proper halting ID in the second case A D V The strings in IllI are of the form w0w w2w 39 39 w2kw k1 or w0wfw2w 39 39 w2k72w k1w2k7 where rum1 h rum2 for all 239 2 07 we is a starting lD7 and w2kl is a proper halting 1D in the rst case Theorem 691 Given any Turing machine M the languages Lg arzd L are eorztert free arzd LM Lg IllI Proof We can construct PDA7s accepting LR and Lil It is easily checked that LM L34 7 Lid 1 As a corollary7 we obtain the following undecidability result Theorem 692 It is undecidable for arbitrary eorzteCUt free grammars G1 arzd G2 whether LG1 LG2 Q Proof We can reduce the problem of deciding whether a partial recursive function is unde ned everywhere to the above problem By Rice7s theorem7 the rst problem is undecidable However7 this problem is equivalent to deciding whether a Turing machine never halts in a proper lD By Theorem 6917 the languages L and Lil are context free Thus7 we can construct context free grammars G1 and G2 so that L LG1 and Lil LG2 Then7 M never halts in a proper 1D iff LM Q iff by Theorem 6917 LM LG1 LG2 Q I Given a Turing machine M7 the language LM is de ned over the alphabet A TU Q U The following fact is also useful to prove undecidability Theorem 693 Given my Turing machine M the language A iLM is eontemt free Proof One can easily check that the conditions for not belonging to LM can be checked by a PDA El As a corollary we obtain Theorem 694 Given my contest free grammar G V E P S it is undecidable whether LG 2 Proof We can reduce the problem of deciding whether a Turing machine never halts in a proper 1D to the above problem lndeed given M by Theorem 693 the language A 7 LM is context free Thus there is a CFG G so that LG A 7 LM However M never halts in a proper lD iff LM Q iff LG A El As a consequence we also obtain the following Theorem 695 Given my two contact free grammar G1 and G2 and my regular language R the following facts hold 1 LG1 2 LG1 Q LltG2gt is undecidable 3 UGO 4 R Q LG2 is undecidable LG2 is undecidable R is undecidable In contrast to 47 the property LG1 Q R is decidable We conclude with a nice theorem of S Greibach7 which is a sort of version of Rice7s theorem for families of languages Let L be a countable family of languages We assume that there is a coding function 0 gt N and that this function can be extended to code the regular languages all alphabets are subsets of some given countably in nite set We also assume that is effectively closed under union and concatenation with regular languages This means that given any two languages L1 and L2 in L we have L1UL2 6 L and CLl U L2 is given by a recursive function of CLl and CLg7 and that for every regular language R7 we have L1R 6 RL1 6 and CRLl and CLlR are recursive functions of CR and C14 Given any language L Q 2 and any string to E 2 we de ne Lw by Lwu 2 lquL Theorem 696 Greibach Let be a countable family of languages that is e ectiuely closed under union and concatenation with the regular lan guages and assume that the problem L 2 is undecidable for L 6 and any given su ciently large alphabet 2 Let P be any nontrivial property of languages that is true for the regular languages and so that if PL holds then PLa also holds for any letter a Then P is undecidable for A Proof Since P is nontrivial for there is some L0 6 so that PL0 is false Let 2 be large enough so that LO Q 2 and the problem L 2 is undecidable for L E L We show that given any L 6 with L Q 2 we can construct a language L1 6 so that L 2 iff PL1 holds Thus the problem L 2 for L 6 reduces to property P for and since for 2 big enough the rst problem is undecidable so is the second For any L 6 with L Q 2 let L1 L02 U 2L Since is effectively closed under union and concatenation with the regular languages we have L1 6 L If L 2 then L1 22 a regular language and thus PL1 holds since P holds for the regular languages Conversely we would like to prove that if L 7E 2 then PL1 is false Since L 31 2 there is some w L But then L1 LU L0 Since P is preserved under quotient by a single letter by a trivial induction if PL1 holds then PL0 also holds However PL0 is false so PL1 must be false Thus we proved that L 2 iff PL1 holds as claimed El Greibach7s theorern can be used to show that it is undecidable whether a context free grammar generates a regular language It can also be used to show that it is undecidable whether a context free language is inherently arnbiguous