### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Limits of Computation 22C 131

UI

GPA 3.87

### View Full Document

## 37

## 0

## Popular in Course

## Popular in ComputerScienence

This 132 page Class Notes was uploaded by Tamia Bernhard on Friday October 23, 2015. The Class Notes belongs to 22C 131 at University of Iowa taught by Hantao Zhang in Fall. Since its upload, it has received 37 views. For similar materials see /class/228041/22c-131-university-of-iowa in ComputerScienence at University of Iowa.

## Popular in ComputerScienence

## Reviews for Limits of Computation

### 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: 10/23/15

Abstraction of Problems Data abstracted as a word in a given alphabet 2 alphabet a finite nonempty set of symbols 226 Limits of Computation 2 all the words of finite length built up using 2 Hamathang Conditions abstracted as a set of words called language 0 Any subset L g 2 is a formal language The University oflowa httpwwwcsumwaeduthhangclal Department ofComputerScience Unknown mpi0ity a Boolean variable true ifa word is the language no othenNIse Given w E 2 and L g 2 doesw E L L Limits m Campmatianrp M5 Limnsatcampmmmnrp m5 Formal De nition of Finite Automata Finite Automata WA finite automaton is a 5tuple Q 2 6 go F where j 7 The simplest computational model is called a nite state 9 Q is a finite set called the states maChme or a mte aummaton 0 2 is a finite set called the alphabet quot Regesetatl39 ns rap ica 6 Q x2 gt Q isthe transition function Tabular n 10 E Q is the start state also called Initial state Mathematical F g Q is the set of accept states also called the nal states Limits m Campmatianrp m5 Limnsatcampmmmnrp m5 Computation of a Finite Automaton Applications The automaton receives the input symbols one by one Finite automata are popular in parser construction of from left to right compilers 9 After reading each symbol M1 moves from one state to 9 Finite automata and their probabilistic counterparts another along the transition that has that symbol as its Markov chain are useful tools for pattern recognition label used in speech processing and optical character recognition 0 When M1 reads the last symbol of the input it produces 0 Markov chains have been used to model and predict the output accept if M1 is in an accept state or reject if price changes in financial applications M1 is not in an accept state lelsm Campmatmnrp m5 lensatcampmatmnrp ms Formal De nition of Acceptance Language of an Automaton 77 7 liLet M QE6q0 F be a finite automaton and lfL isthe set of all stringsthat a finite automaton M w 1102an be a string over 2 accepts we say that L is the language of the machine Then M acceptSw ifa sequence of states r0 r1 r7 exist M and wr39te MM L39 in Q such that the following hold 0 An automaton may accept several strings but it always recognizes only one language 0 If a machine accepts no strings it still recognizes one language namely the empty language Q h 1 T0qo N 602311241 T241170 01tttn71 3 Tu E F Condition 1 says where the machine starts bb Condition 2 says that the machine goes from state to state according to its transition function 6 b Condition 3 says when the machine accepts its input if it ends up in L an accept state lelsm Campmatmnrp M5 lensatcampmatmnrp ms Designing Finite Automata Regular Languages 0 Whether it be of automaton or artwork design is a i i We say that a finite automaton M recognizes the language creative process Consequently it cannot be reduced to L if L w l M accepts w a simple recipe or formula The approach Definition A language is called regularlanguage ifthere exists 1 Identify the finite pieces of information you need to a finite automaton that recognizes it solve the problem These are the states 3 Identify the condition alphabet to change from one state to another 1 Identify the start and final states 0 Add missing transitions Limitsmcampmmmn 7 ms Limnsatcampmatmnrp 9amp5 Regular Expressions Operations on Regular Languages if Three base cases j ii Let A and B be languages We define regular operations Q is a regular expression denoting the language Q union concatenation and star as follows e is a regular expression denoting the language 6 Uquoti quot A U B 1 t 95 6 AV 95 E B 0 For any a E E a is a regular expression denoting the c quot atequotati quot A O B 951 W E A A 1 E B language a 1 Star A 1112xk l k 2 0 x E A1z39 k2 Note 9 Three recursive cases If n and M are regular 1 Because any numberquot includes 0 E E 14 no matter expressions denoting languages L1 and L2 respectively What A is then 2 A denotes A o A 1 Union 71 U m denotes L1 U L2 Concatenation rlrg denotes Lng L 0 star r f denotes L f Limitsmcampmmmn 421MB lensm Computatioan ms Closure under Complementation Closure under Intersection 0 Theorem That class of regular languages is closed under Theorem That class of regular languages is closed under complementation intersection 0 Proof For that we will first show that if M is a DFA that 9 Proof Use crossproduct construction of states recognizes a language B swapping the accept and nonaccept states in M yields a new DFA that recognizes the complement of B L ertsatcampmatmn 7 ms lensat Campmatmnrp ms Two ways to Introduce Nondeterminism Nondeterminism 0 More choices for the next state Zero one or many j 7 So far in our discussion every step ofa finite arrows may exit from each state automaton computation follows in a unique way from 9 A state may change to the next state without spending the preced39ng Step39 an input symbol etransitions We call this a deterministic computation In a nondeterministic computation choices may exist for the next state at any point Nondeterminism is a generalization of determinism hence every finite automaton is a nondeterministic finite automaton NFA 7 b b ertsatcampmatmn 421MB ertsat Computater 7 ms Tree Computation of NFA A way to think of a nondeterministic computation is as a tree of possibilities 0 The root ofthe tree corresponds to the start of the computation 0 Every branching point in the tree corresponds to a point in the computation at which the machine has multiple choices 0 The machine accepts if at least one of the computation branches ends in an accept state leltsmcampmmmn 7 1M5 Formal De nition of NFA 1 An NFA is a 5tuple Q7 267 F where bb 1 Q is a finite set called the states 3 E is a finite set called the alphabet n max mewww where 79Q is the power set on 9 10 E Q is the start state also called initial state 1 F g Q is the set of accept states also called the nal states In a DFA transition function is 6 Q X E gt Q notation For any alphabet E 26 E U 6 lensm Campmatmn 7 ms Computation by an NFA liLet N Q 26410 F be an NFA and w a string over 2 We say that N acceptsw ifw a1a2am 1139 6 26132 m and a sequence of states r0 r1 rm exists in Q such that 1 7 0 10 2 n1 E 6Ti7ai1f0ri 01777 7 1 3 rm 6 F 9 Condition 1 says the machine s starting state 5 Condition 2 says that state n1 is one ofthe allowable new states when N is in state m and reads 1H1 Note that 6m 1H1 is a set 5 Condition 3 says that the machine accepts the input if L the last state is in the accept state set mes m Cam Pmatmn 7 in ms b b b 55 Why NFA 7 Constructing NFA is sometimes easier than constructing DFA An NFA may be much smaller than a DFA that performs the same task Computation of NFA is usually more expensive than that of DFA Every NFA can be converted into an equivalent DFA NFA provides good introduction to nondeterminism in more powerful computational models lelsm Campmatmn 421MB Application of NFA Now we use the NFA to show that collection of regular languages is closed under regular operations union concatenation and star Theorem 125 145 The class of regular languages is closed underthe union operation Theorem 126 147 The class of regular languages is closed under concatenation operation Theorem 149 The class of regular languages is closed under star operation b b b mus m Cam Pmatlari 7 in ms Equivalence of NFA and DFA Theorem Every NFA automation has an equivalent DFA to recognize the same language 0 DFAs and NFAs recognize the same class of languages This equivalence is both surprising and useful o It is surprising because NFAs appears to have more powerthan DFA so we might expect that NFA recognizes more languages n It is useful because describing an NFA for a given language sometimes is much easier than describing a DFA Limnsat Campmatianrp 21 as Equivalence of NFA and DFA r The Formal Proof j Let N Q 26410 F be the NFA recognizing the language A We construct the DFA M recognizing A 0 Before doing the full construction consider first the easier case when N has no 6 transitions mus m Cam Pmatlari 7 in Ms r Question s the class of languages recognized by NFAs closed under complementation m its m cm Pmatlari 7 in ms Corollary 140 Equivalence of NFA and DFA A language is regular iff some NFA recognizes it The Formal Proof P f Let N Q 26410 F be the NFA recognizing the language r 39 A We construct the DFA M recognizing A quot If a language A 395 re 9 39z d by an NFA ther A IS 1 Before doing the full construction consider first the recognized by the DFA equwalent hence A Is regular easier case when N has no 6 transitions 9 If a language A is regular it means that it is recognized by a DFA But any DFA is also an NFA hence the Then we conS39derthe E trans39t39ons39 language is recognized by an NFA Notation For any R g Q define ER to be the collection of states that can be reached from R by going only along 6 transitions including the members of R themselves Formally ER RU q E Q l 371 6 R73 rk E Qn1 E 6m ewk q b lelismcampmmmn 7 2m lensm Computation in ms Consider the decidable language A 07 17 in 2 0 and the Example computation following TM M1 deciding A M1 quotOn input string w 1 Scan acrossthe tape and reject if a 0 is found to the right ofa 1 2 Repeat as long as both Os and 1s remain of the tape a Scan acrossthe tape crossing offa single 0 and a single 1 0 If Os still remain after all 1s have been crossed off or is 1s still remain after all Os have been crossed off reject Otherwise if neither Os nor 1s remain of the tape accept Limitsat Computatioan m5 22czl31 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclal The University of Iowa Department of Computer Science Time Complexity Limnsatcampmmmnrp ms N 00 Simplifying Conventions 7 The running time of an algorithm is a function ofthe length ofthe string representing the input on the algorithm In worstcaseanalysis we consider the longest running time of all inputs ofa particular length In averagecase analysis we consider the average of all the running times of inputs of a particular length Limitsat Computatioan ms How much time does take M1 to decide A It is 0 Analyzing an Algorithm 7 Number of steps the TM has this may depends on several parameters Limnsatcampmmmnrp m5 BigO and smallO notation b The exact running time of an algorithm may be a complexexpression Therefore usually this is just estimated b One convenient form of the estimation is so called asymptotic analysis which determines the running time ofthe algorithm on large inputs b In the asymptotic analysis one may consider only the highest order term ofthe expression forthe running time ofthe algorithm disregarding both the coefficient ofthat term and any lower order terms b This is valid because the value of the highest order term dominates the value of other terms on large inputs leism Computatioan m5 Time Complexity of a TM Let M be a deterministic Turing machine that halts on all inputs The running time or time complexity of M is a function f N gt Nwhere fn isthe maximum number of steps that M uses on any input of length n 1 If fn is the running time of M we say that M runs in time fn and that M is an fn time Turing machine Customarily n represents the length ofthe input Limnsatcampmmmnrp ms Formally r Let f and g be functions g N gt R We say that fn Ogn if positive integers c and n0 exist such that W 2 no n S 0901 When fn Ogn we say that gn is an upperbound for fn more precisely gn is an asymptotic upper bound for fn which emphasizesthe suppression of constant factors leism Computatioan m5 7 r Examples Consider the function fn 6713 2712 107 100 j l Disregarding the coefficient 6 we say that f is asymptotically at most 8 TL b The asymptotic notation or bigO notation for describing the estimation defined by fn is fn 0713 Limnsatcampmmmnrp ms Examples Intuitively 1 When we use logarithms because 095 n 1092 711092 12 the base n Ogn mans that f is less then or equal to 9 if needs not be SPBCified ThUSl if we disregard differences up to a constant factor f2 3711092 5711092 092 2 we have Mn 00110971 1 One may think at O as representing a constant 9 In practice most functions f encountered in algorithm analysis have an obvious highest order term hn In that case fn Ohn L l L Limilsatca lpmmmn 7 ms Limnsatcampmmmnrp ans Polynomial and Exponential Bounds Expressions of bigO T 77 0 Bounds ofthe form n0 for c gt 0 are called polynomial b Consider fn 00 n where each occurrence of 0 represents a different suppressed constant Because 0712 dominates 0n fol 0012 0 When 0 occurs in the exponent as in fn 200 the same idea applies ie fn 026 for some constant 6 However if we also have gn 00 it cannot be concluded that fol 0yn For expressions of the form fn 20009 gt using the identity 71 21092 7 ie n6 261092 we can see that 20009 n represents an upper bound of n6 for some 6 Bounds ofthe form am for a gt 1 06 gt 0 are called exponen albounds b b Because 01 represents a value that is never more than a constant 7101 represents the value 716 for some 6 L l L Limilsatca lpmmmn 7 ms Limnsat Computation in ms Examples Check that 1 071 2 n 071 loglogn 3 n loglogn 071 10901 4 n 10971 00 5 n2 0713 6 fn is never ofn Limitsmcampmatian 7 ms SmallO notation BigO notation says that a function is asymptotically no more than another function 0 SmallO notation says that a function is asymptotically less than another function Formally for g N gt R we say that fn ogn if itmnmggg 0 That is fn 0gn means that for any real 0 gt 0 there exists no such that fn lt cgn for all n gt 710 b Limnsat Campmatianrp ms On input of length n Consider each of the three stages separately 7 1 In stage 1 the machine scans the tape in 71 steps to verify that the input is of the form 01 repositioning the tape atthe left end uses anothern steps 80 the total number of steps is 271 ie On 2 Each scan of the tape in stage 2 and 2a is performed in On Because each scan crosses off a 0 and a 1 at most 712 scans occur le the total number of steps is n2On 0712 3 In stage 3 the machine makes a single scan to decide whether to accept or reject taking 0n steps Total number of steps is 0n 00 0n 00 L Limitsmcampmatian 421555 Analyzing Algorithms rConsider the TM algorithm M1 that decides the language j A 0 1 l n 2 0 M1 quotOn input string w 1 Scan across the tape and reject if a 0 is found to the right ofa 1 2 Repeat as long as both 0s and 1s remain of the tape a Scan across the tape crossing offa single 0 and a single 1 3 If 0s still remain after all is have been crossed off or is 1s still remain after all 0s have been crossed off reject Otherwise if neither 0s nor 1s remain of the tape accept Limnsat Campmatian 7 tS S M2 a TlMEn log 71 TM Notations M2 quotOn input string wi l l Let t N gt N be a function The time complexity class 1 Scan acrossthe tape and reject if a 0 is found to the right of a1 TIMEUW is the COIleCtlon Of languages that are deCldable 2 Repeat as long as some 0 s and some 1 s remain on the tape by an Cam tlme TM39 a Scan acrossthe tape checking whetherthe total number of 0 s and 1 s remaining on the tape is even or odd If it is odd reject b Scan again across the tape crossing every other 0 starting with I Since language A 0 1 L l n 2 0 is decided by M1 in 00 steps A e TIMEn2 0 TlMEn2 contains all languages decidable in 00 time th f39 to dth 39 ff th 1 t t39 39thth r If an en crossmg 0 every 0 er 8 ar mg WI 6 I lsthere a TM that decides A asymptotically faster leis A in TlMEtn for tn 0012 One can cross 2 0s and 2 1 s in stage 2 3 If no 0 5 and n0 1 5 rema39n 0ftne tapev accept omen 59 91901 which cuts the number of scans by half but running time does not change L l l Limitsmcampmatian 421555 Limnsat Campmatian rp17 5 Deciding A in 901 liThe following twotape TM M3 decides A in lineartime ie l7 in On time Analysis 1 Stage 1 takes 0n steps j 2 Stage 2 takes 1 1092 nOn 0n 09 71 steps M3 quotOn input string w on tape 1 3 Stage 3 takes 0n steps 1 Scan acrossthe tape 1 and reject If a 0 Is found to the right of a 1 Total number of Steps is asymptotically 0011092 71 that is 2 Scan acrossthe 0 s on tape 1 until the first 1 at the same time copy A E TIMEW log n the 0 s on tape 2 3 Scan acrossthe 1 s on tape 1 until the end of the tape is discovered 0 91 any language that can be deClded in 001109 71 on a Single39tape TM For won 1 read on tape 1 Cross Off a 0 on tape 239 If a 015 are is regular since A is not regular no faster algorithm performed by a single crossed off before all 1 are read reject tape TM exists to decide it 4 If all 0s have been crossed off accept If any 0 s remain reject L l l mus m Cam Pmatian 7 in ms Limitsat Campmatian 7 was Observations Conclusions There is an important difference between complexity theory 1 M1 using one tape decides A in 0n2 and ComPUtab39l39ty theory M2 using one tape decides A in On log n 0 The ChurchTuring thesis impliesthat all reasonable M3 using two tapes decides A in 001 models of computation are equivalent ie for each model 0 there is an equivalent model 0 b In complexity theory the choice of model affects the COHCIUSionl time compleXitY Of A 0 onetape TM is time complexity ofthe language decided by that model ie languages decidable by model C in lineartime are not necessarily decidable in lineartime by the equivalent model 0 On log n time complexity of A on twotape TM is 0n Limitsmcampmmmn 7 ms Limnsal Computation 7 21 as Theorem 78 Complexity Relations Let tn be a function where tn 2 n Then every tn time rComplexity relations among models show how choice of multitape Turing machine has an equivalent 905201 time computational model can affect the time complexity of singletape Turing machine languages For that we consider three computation models 0 Singletape Turing machine Proof idea We know how to convert a multitape TM M into a singletape l Multipletape Turing machine TM Sthat simulates M We show that each step ofM by can be simulated n Nondeterministic Turing machine by S in time Otn Since there are Otn steps performed by M there will be 0t2n steps performed by S L Limitsmcampmmmn 7 ms Limilsal Computation 7 ms Analyzing S Proof of Theorem 78 I For each step of M S makes two passes over the active portion of its For M a ktape TM that runs in tn time the singletape TM S operates tape first to obtain the info necessary to determine the next move as follows and second to carry out the move Initially S puts its tape into the format that represents all the ktapes The upperbound of the length ofthe active portion of S s tape isthe of M and then simulates M sum of the length of active portions of Ms k tapes which are bounded by tn ie upperbound ofthe active portion of S s tape is 0mm b N To simulate one step of M S scan all the info stored on its tape to determine the symbol under M s heads 0 Then S makes another pass over its tape to update the tape contents and head positions 5 If one on Ms heads moves rightward onto a previously unread position on its tape S must increase the amount of space by shifting a portion of its tape one cell to the right L l l lelisatcampmatlan 7 ms Llrllltsm Campmatlarl 7 ms Corallary Simulation time liLet tn and 5n be functions where 15n7 5n 2 n If 3 71 To simulate each of Ms steps S performstwo scans each using 0 t39 t fM39 39 ltdbS39O t39 multitape Turing machine takes tn time and 5n space for WW Ime Ie one sepo 398 S39muae y m OW 39me l Sine by assumption M perform tn steps total time taken by S to any Input 0f length m then there IS an eqUIValent 00500800 simulate M is 0001 taken bythe initial step plus n 0001 to time singletape Turing machine perform the simulation ie time complexity of S is 0t2n L l l lelisatcampmatlan 7 ms Llrllnsm Campmatlanrp ms Deterministic and nondeterministic TM Nondeterministic TM Let N be a nondeterministic TM that is a decider The run T Datermmm Nomie33 T ning time of N is the function f N a N Where fn is the M hccept m maximum number of steps that N makes on any branch of its computation on any input oflength n as shown in Figure 1 L i acceptreject l raiect L Figure 12 Measuring deterministic and nondeterministic time Limits mew Pmatiari 7 suns Limitsat Computation 7 ms Theorem 711 Note T 7 Let tn be a function where tn 2 n Then every tn time 7 0 Definition ofthe running time of a nondeterministic TM nondeterministic singletape Turing machine has an is not intended to correspond to any realworld equivalent 20 time deterministic singletape Turing COl39 lotlting deVice maCh39ne The running time ofa nondeterministic TM is a useful abstraction that assists in characterizing the complexity Proofidea Let N be a nondeterministic TM running in time tn We con of an important Class of computational problems struct a deterministic TM D that simulates N by searching N s nondeter ministic computation tree Limits mew Pmatiari 7 ms Limitsat Computation 7 31 as The Simulation Proof Visit all nodes at depth d of the computation tree before going to the depth d 1 starting with the root total number of nodes is less then Computation tree On input of length 71 every branch of N s nondeterministic twice the number of leaves ie this is bound by Ob lt gt computation tree has a length at most ml 2 Time for Starting from the met and traveling down to 5 Ode is 0901 2 Every node in the tree can have at most 12 children where b is the 3 Therefore the running time of D is 0btltngt 20001 maximum number of legal choices given by N s transition function 0 an Note TM D has three tapes Converting D to a singletape by previous Hence the tetal number Of leaves In the tree 398 at mOSt b 39 theorem the running time at most squares Thus we have 209002 200471 20601 L l l leltsmcampmmmn 7 ms lensm Campmatlanrp ms Summary r Let t N gt N be a function The time complexity class TlMEtn is the collection of languages that are decidable by an Otn time TM The time complexity class NTlMEtn is the collection of languages that are decidable by an Otn time NTM 7 TIMEtn C NTIMEtn C TIME2 quot for some con stantc lensm Campmatlan 7 sans Reduction Examples To prove that a problem P is solvable by reduction method 7 proceeds as follows J Find a problem Q known to be solvable Assume than P is solvable by a TM Mp Use the TM Mp to construct a TM MQ that solve Q a Encode every instance of the problem Q as an instance Qp of probelm P b Use Mp to solve Qp Since it is known that Q is unsolvable MQ cannot exists Hence Mp cannot exists either lelsm Campmatmnrp m b b b 0 Suppose that one wants to find hisherway in a city A This would be easy if one had a city map Hence problem A is reduced to the problem of finding a city map problem B 22c39 lelts 0f computatlon 0 Problem A traveling from Iowa City to Paris reduces to problem B Hantao Zhang buying a plain ticket between two cities httpwwwcsumwapduthhangclsl 0 Problem A measuring the area ofa circle reduces to problem B The Universit o owa measuring r the circle radius which reduces to problem C De artmem ofComy utersmence performing m2 p p 0 Problem A solving a system of linear equations reduces to problem RedUCibility B triangulating a matrix Methodology Observatlons When problem A is reducible to problem B solving A cannot be harder than solving B because a solution to B gives a solution to A If A is reducible to B and B is decidable then A is decidable because a solution to B solves A lfA is undecidable and reducible to B then B is undecidable because if B would be decidable then Awould what is a contradiction lensatcampmmmnrp m HALTTM is undecidable Theorem 51 Proof idea by contradiction Assume that the TM R decides HALTTM and use R to construct S a TM that decides ATM S quotOn input ltMwgt an encoding of M and a string w 1 2 3 4 L Run TM R on input ltMwgt lfR rejects ie M loops on w reject lfR accept ie M halts on w simulate M on w until it halts If M has accepted accept if M has rejected reject musm Campmatmnrp m Application 1 Problem P the halting problem HALTTM is the problem of determining whether a Turing machine M halts on an input 10 HALTTM MiLID l M23 1 TM M halts on w b Unsolvable problem Q we have established the undecidability of ATM HiLID l M is a TM M accepts w the problem of determining whether a TM M accepts a string 10 We use the undecidability of ATM to show that b HALTTM is undecidable by reducing ATM to HALTTM Limnsatcampmmmnrp 5m b Constructing TM S Bad idea Run R on M If it accepts then we know that LM 2 j and therefore M does not accept w If R rejects LM 7 I but we don t know if M accept or not w hence we need another idea Good idea run R on a modification M1 of M that guaranteesthat M1 rejects all strings except w That is LM1 w if w e LM and LM1 I ifw g LM So LM1 I iffw g LM R can test if LM1 I musm Campmatmnrp m Emptiness Problem for TM rETM l M25 1 TMALM 9 Theorem 52 ETM is undecidable Proofidea I Assume that ETM is decidable and let TM R deciding ETM 9 Show that ATM ltMwgt l M is a TM and w isa string is decidable by constructing TM S that decides ATM 7 Limnsatcampmmmnrp m Proof continuation Proof Assume that ETM is decidable by R and construct TM S The modified machine M1 is defined by that decides ATM as follows M1 quotOn input as S quotOn input ltMwgt an encoding of a TM M and a string w 1 lfz w reject 1 Use the description of M and w to construct M1 2 lfz w run M on input w and if M accepts acceptquot 239 RU R0 mm ltM1gt Note M1 has 10 as part of its description It conducts the test 3lfR t 39 fquotfR 39 t tquot accep r6160 5quot rejec 8 8006p 95 w by scanning the Input and comparing it character by Conclusion character With u If B were a decider for ETM S would be a decider for ATM But a decider for ATM cannot exists hence B does not exist and ETM is undecidable Note ETM is coTuringrecognizable leltsmcampmmmn 7 mm lensatcampmatmnrp am Theorem 53 TM and Regular Languages liREGULARTM is undecidable j 7 0 Can a TM recognize a language recognized by a j Proof idea reduce to ATM ie assume that REGULARTM f39mpler CgmpL39tat39onal mOdel39 SUCh as a regmar is decidable by a TM R and use this assumption to anguage39 construct S that decides ATM 0 For example REGULARTM isthe problem oftesting Idea fors take input M710 and modify M so that the whether a given TM has an equivalent finite automaton resulting TM M2 recognizes a regular language iff M 9 This is the same as testing whether a TM recognizes a accepts 102 regular language 0 M2 recognizesthe nonregular language 0 1 L l n 2 0 if M does not accept w REGULARTM l M is a TM A LM is regular 0 M2 recognizesthe regular language 2 ifM accepts w L leltsmcampmmmn 7 12m lensm Campmatlari 7 ma Proof Let R be a TM that decides REGULARTM We construct TM S that decides ATM as follows S quotOn input ltMwgt where M is a TM and w is a string 1 Construct TM M2 bythe procedure M2 quotOn input as a If I 07 1 for some n 2 0 accept b If I 7 Ont run M on w and if M accepts w then accept 2 Run Ron M2 3 If R accepts accept if R rejects rejectquot L Limitsatcampmmmn 7 1m Constructing M2 S constructs M2 by the following procedure 9 M2 accepts automatically all strings in 0 1 l n 2 0 0 In addition if M accepts u then M2 accepts all other strings Limnsat Campmatianrp 13m Rice s Theorem Exercise 528 liLet P be any problem about Turing machines As usual we express P as 7 a language ie P is the language of P Assume that P satisfies the following two properties 1 For any TMs M1 and M2 where LM1 LM2 we have M1 6 P iff M2 6 P le membership ofa TM M in P depends only on the language of M 2 There exist TMs M1 and M2 where M1 6 P and M2 g P le P is nottrivial it holds for some TMs but not for all Show that P is undecidable L Limitsatcampmmmn 7 lBQCl r 0 If R decides REGULARTM then S decides ATM I But ATM is undecidable ie S cannot exists Conclusion 7 1 Hence R cannot exists either and REGULARTM is undecidable Limnsat Campmatianrp lSQCl b Proof continuation Ifw 6 ATM LMw LM1 and MW should be accepted by Tp since M1 6 P Ifw g ATM LMw I LT0 and MW should be rejected by Tp by the assumption that T0 g P Conclusion 10 6 ATM iff M1 6 P However since ATM is undecidable hence P is not decidable either lellsmcampmatlan 7 m Proof 1 Suppose P is a decidable language satisfying properties 1 and 2 I Let Tp be a TM that decides P V thout loss of generality assume that T0 with LT0 2 T0 g P if T0 6 P we can considerP I Since P is not trivial there exists TM M1 with M1 6 P Then the following TM X could decide ATM X quotOn input ltMwgt Construct a TM Mw that accepts input 1 iff both M accepts w and M1 accepts 1 Run Tp on MW lf Tp accepts accept otherwise rejectquot N lensm imputatan 7 17m b b Using Other Reductions 7 Sometimes reducing from other different from ATM undecidable languages such as ETM is more convenient Example testing the equivalence of two TM EQTM M1M2gt l M1M2 are TMS A LM1 LM2 can be proven undecidable by reduction from ETM mes m Cam Putatan 7 p 2cm Fact r Both conditions in Rice s theorem are necessary for proving that P is undecidable Proof 1 Let P ltM l M is a TM with 5 states P is nontrivial so it satisfies the condition 2 of Rice s theorem But in this case P could be decided by checking the number of states of the input TM M N Let P be the empty set Then it does not contain any TM and so it satisfies the condition 1 of Rice s theorem But in this case P can be decided by a TM that always rejects Therefore both properties in Rice s theorem are necessary for proving that P is undecidable lensm Campmatlanrp 19m Proof Theorem 54 Let TM R decide EQTM Construct TM S to decide ETM as EQTM is undecidable follows S quotOn input M where M is a TM Proof idea show that if EQTM were decidable then ETM also 1 would be decidable by giving a reduction from ETM to Run R on input ltMM1gt where M1 is a TM that rejects all inputs EQTM 2 lfR accepts accept if R rejects rejectquot 9 ETM is the problem of testing whetherthe language ofa TM is empty Note If R decides EQTM then S decides ETM but ETM is 0 EQTM is the problem of testing whether the languages of two TMs undecidable hence R cannot exists are the same If one of these languages is empty we end up with trying to solve ETM 0 Hence ETM is a special case of EQTM mus m Cam Pmatian 7 p 2m Limnsat Campmatianrp 21 m Note 0 Because M1 rejects all strings if R accepts it means j that language of M is the same with language of M1 ie empty If R rejects it means that language of M is not equal with the language of M1 which is empty That is language of M is not empty le ns m Cam Pmatian 7 p 2m Reduction Examples 1 Suppose that one wants to find hisherway in a city A This would be easy if one had a city map Hence problem A is reduced to the 22c 1 of Computation problem of finding a city map problem B 0 Problem A measuring the area ofa circle reduces to problem B Hantao Zhang measuring r the circle radius which reduces to problem C hccpzmamasumwaeduhzhangc131 performing m2 The University of Iowa 0 Problem A solvmg a system of linear equations reduces to problem Department of Computer Science B triangulating a matrix 0 Problem A proving a set is uncountable reduces to problem B Reducibility establishing a correspondence betweeb this set and the set of reals Limits m Campmatmnrp 2m Limnsatcampmatmrirp m Methodology Observations T 7 T 7 Convention solvable means either decidable or Turingrecognizable b Reduction is a terminating process When problem A is reduced to problem B solving A To prove that a problem Q IS solvable by r6dUCt0n methOd cannot be harder than the sum of reduction and solving proceeds as follows B because a solution to B gives a solution to A 1 Find a PFOb39em P known to be SOIVab39e If A is reduced to B and B is decidable then A is 2 Assume that P is solvable by a TM Mp decidable because a solution to B solves A in finite number of 3 Use the TM Mp to construct a TM MQ that solve Q Steps 0 lfA is undecidable and reducible to B then B is a Encode every instance q of the problem Q as an instance qp of probelm P undeCIdable because ifB would be decidable then A would b Use MP to solve qp and return the result Whioh is a Comradionon Limits m Campmatmnrp m Limnsatcampmatmrirp 3m Appllcatlon Methodology 0 Problem P the halting problem HALTTM is the Convention unsolvable means either undecidable or not problem of determining whether a Turing machine M Turingrecognizable halts 0 an mm 10 I To prove that a problem P is unsolvable by reduction HALTTM MW l M 25 a TM M haltS 0 10 method proceeds as follows 0 Unsolvable problem Q we have established the 1 Find a probiem Q known to be unsoivabie undecidability of 2 Assume that P is solvable b a TM M ATM M7 llgt l M is a TM Maccepts w y P the problem of determining whether a TM M accepts a 3 use the TM MP to con rm a TM MQ that SOIVe Q3 string w a Encode every instance q of the problem Q as an instance qp of b l P 9 We use the undeCIdability of ATM to show that pro em HALTTM is undecidable by reducing ATM to HALTTM b Use MP to some 4P 4 Since it is known that Q is unsolvable MQ cannot exists Hence MP cannot exists either and P is unsolvable Emptlness Problem for TM Theorem 51 WETM M l M25 1 TMALM 0 j liHALTTM is undecidable W Theorem 52 ETM is undecidable Proof idea by contradiction Proofidea Assume that the TM R decides HALTTM and use R to construct S a TM 39 that decides ATM 0 Assume that ETM is decidable and let TM R deciding ETM S quotOn input ltMwgt an encoding of M and a string w 9 Show that ATM Mwgt l M is a TM and w is a string 1 RU W R 0 39 PUt ltMvwgtv is decidable by constructing TM Sthat decides ATM 2 lfR rejects ie M loops on w reject 3 lfRaccept ie M halts on w simulate M on w until it halts 4 lfM has accepted accept if M has rejected reject Proof The modified machine M1 is defined by M1 quotOn input 2 1 Ifz 7 w reject 2 Ifz w run M on input w and if M accepts acceptquot Note M1 has 10 as part of its description It conducts the test as w by scanning the input and comparing it character by character with w Limits avcam Pmatian 421nm Constructing TM S 1 Bad idea Run R on M If it accepts then we know that LM Z and therefore M does not accept w lfR rejects LM 7 I but we don t know if M accept or not w hence we need another idea b Good idea run R on a modification M1 of M that guaranteesthat M1 rejects all strings except w That is LM1 w if w e LM and LM1 2 if w g LM So LM1 2 iff w g LM R can test if LM1 I Limnsatcampmmmnrp 9m TM and Regular Languages r 9 Can a TM recognize a language recognized by a simpler computational model such as a regular language 9 For example REGULARTM isthe problem ofte whether a given TM has an equivalent finite auto 7 sting maton This is the same as testing whether a TM recognizes a regular language REGULARTM l M is a TM A LM is regular Limits avcam Pmatian 7 12m U Proof continuation 7 ssume that ETM is decidable by R we construct TM S that decides ATM as follows S quotOn input ltMwgt an encoding of a TM M and a string w 1 Use the description of M and w to construct M1 2 Run R on input M1 3 If R accept rejects if R rejects acceptquot Conclusion If B were a decider for ETM S would be a decider for ATM But a decider for ATM cannot exists hence B does not exist and ETM is undecidable Note ETM is coTuringrecognizable Limnsal Campmatian 7 m Constructing M2 S constructs M2 by the following procedure 9 M2 accepts automatically all strings in 0 1 l n 2 0 0 In addition if M accepts u then M2 accepts all other strings leltsatcampmatmn 7 m Theorem 53 REGULARTM is undecidable Proof idea reduce to ATM ie assume that REGULARTM is decidable by a TM R and use this assumption to construct S that decides ATM Idea for S take input Mm and modify M so that the resulting TM M2 recognizes a regular language iff M accepts w 1 M2 recognizesthe nonregular language 0 1 L l n 2 0 ifM does not accept w 1 M2 recognizesthe regular language 2 ifMaccepts w lensal Campmatmnrp 13m r Conclusion 9 If R decides REGULARTM then S decides ATM But ATM is undecidable ie S cannot exists 7 0 Hence R cannot exists either and REGULARTM is undecidable leltsatcampmatmn 415m Proof liLet R be a TM that decides REGULARTM We construct W TM S that decides ATM as follows S quotOn input ltMwgt where M is a TM and w is a string 1 Construct TM M2 bythe procedure M2 quotOn input as a If I 07 1 for some n 2 0 accept b If I 0711 run M on w and if M accepts w then accept 2 Run Ron M2 3 lfR accepts accept if R rejects rejectquot lensal Campmatmnrp 15m Proof 1 Suppose P is a decidable language satisfying properties 1 and 2 I Let Tp be a TM that decides P V thout loss of generality assume that T0 with LT0 2 T0 g P if T0 5 P we can considerP 0 Since P is not trivial there exists TM M1 with M1 6 P Then the following TM X could decide ATM X quotOn input Mw M1 accepts 1 N Construct a TM Mw that accepts input 1 iff both M accepts w and Run Tp on MW lf Tp accepts accept otherwise rejectquot Limits mean Pmatian 7 lam Rice s Theorem Exercise 528 Let P be any property about Turing machines As usual we express P as a language ie P is the language ofTMs having property P Assume that P satisfies the following two properties 1 For any TMs M1 and M2 where LM1 LM2 we have M1 6 P iff M2 6 P e membership ofa TM M in P depends only on the language of M 2 There exist TMs M1 and M2 where M1 6 P and M2 g P e P is nottrivial it holds for some TMs but not for all Show that P is undecidable Liriinsai Campmatianrp 17m Fact r that P is undecidable Proof Both conditions in Rice s theorem are necessary for proving Let P M l M is a TM with 5 states P is nontrivial so it satisfies the condition 2 of Rice s theorem But in this case P could be decided by checking the number of states of the input TM M N Let P be the empty set Then it does not contain any TM and so it satisfies the condition 1 of Rice s theorem But in this case P can be decided by a TM that always rejects Therefore both properties in Rice s theorem are necessary for proving that P is undecidable Limits m Cam Pmatian 7 2cm r Proof continuation 1 Ifw 6 ATM LMw LM1 and MW should be accepted by Tp W since M1 6 P l Ifw g ATM LMw I LT0 and MW should be rejected by TP bythe assumption that T0 g P Conclusion 10 6 ATM iff M1 6 P However since ATM is undecidable hence P is not decidable either Liriinsai Campmatianrp 19m Theorem 54 EQTM is undecidable Proof idea show that if EQTM were decidable then ETM also would be decidable by giving a reduction from ETM to EQTM 0 ETM is the problem of testing whetherthe language ofa TM is empty 0 EQTM is the problem of testing whether the languages of two TMs are the same If one of these languages is empty we end up with trying to solve ETM 5 Hence ETM is a special case of EQTM mus m Cam Pmatiari 7 22m Using Other Reductions Sometimes reducing from other different from ATM undecidable languages such as ETM is more convenient Example testing the equivalence oftwo TM EQTM M1M2gt i M1M2 are TMs A LM1 LM2 can be proven undecidable by reduction from ETM Limnsal Campmatianrp 21 m Note T 7 9 Because M1 rejects all strings if R accepts it means that language of M is the same with language of M1 ie empty 1 If R rejects it means that language of M is not equal with the language of M1 which is empty That is language of M is not empty 1 EQTM is neither Turingrecognizable nor coTuringrecognizable mus m Cam Pmatiari 7 2m Proof r Let TM R decide EQTM Construct TM S to decide ETM as follows S quotOn input M where M is a TM 1 Run R on input ltMM1gt where M1 is a TM that rejects all inputs 2 If R accepts accept if R rejects rejectquot Note If R decides EQTM then S decides ETM but ETM is undecidable hence R cannot exists Limnsal Campmatian 7 23m ContextFree Grammars CFG 9 There are languages such as 0 1 l n 2 0 that cannot be described specified by finite automata or regular expressions 5 Contextfree grammars provide a more powerful mechanism for language specification b Contextfree grammars can describe features that have a recursive structure making them useful beyond finite automata lellsm Computatioan m 22c131 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclal The University of Iowa Department of Computer Science Limnsatcampmmmnrp ma Example 0 CFG G1 has the following specification rules A 0A1 A A D Nonterminals ofCFG G1 are A B and A is the start symbol 9 Terminals ofCFG G1 are 01 lellsm Computatioan m 7 A contextfree grammar is a 4tuple V E R S where ONT 5 Formal De nition of a CFG 7 V is a finite set of symbols called the variables or nonferrninas E is a finite set of symbols disjoint from V called terminals R is a finite set of rules or specification rules of the form 15 a Th5 where lhs e V T715 6 V U E S e V isthe start variable Limnsatcampmmmnrp m Example derivation tree Language speci cation The derivation tree ofthe string ooo111 using CFG G1 is in A grammar is used for a language specification by Figure 1 generating each string ofthe language in following manner Write down the start variable it is the lhs of the first specification rules unless specified otherwise M A A i Find a variable that is written down and a rule whose lhs is that l variable Replace the written down variable with the Th5 of that rule A B 0 Repeat step 2 until no variables remain in the string thus generated Note The sequence of substitutions used to obtain a string using a CFG is called a derivation and may be represented by a tree called a derivation Fig U re 12 Derivation tree for 00 o1 11 free or a parse tree L l l Limitsat Campmatmnrp m lensatcampmatmnrp 5m CFG G2 Note T 77 The CFG G2 specifies a fragment of English 0 All strings ofterminals generated in this way constitute the language specified by the grammar lt5ENTENCE 7 NOUN 7 PHRASE ltVERB 7 PHRASE lt ltNOUN7 PHRASE 7 ltCP7 NOUN l ltCP7 NOUNltPREP 7PHRASE we write 1a for the language generated by the ltVERB7PHRASE 7 ltCP7VERB l ltCP7VERBltPREP7PHRASE grammar G Thus Gl 0n1n n 2 0 ltPREPPHRA5Egt ltPREPgtltCPrNOUNgt 0 A language generated by a contextfree grammar ltCPrN0UNgt ltARTICLEgtltNOUNgt CFG is called a ContextFree Language CFL ltCP 7 VERB 7 ltVERB ltVERB ltNOUN 7 PHRASE ltARTICLE 7 a l the ltNPUNgt 4 boy lgi39rl l flower ltVERBgt 4 touches l likes l sees ltPREP 7 with L l l Limitsat Campmatmnrp am lensatcampmatmnrp ma Direct derivation Example derivation with G2 n If 14010 6 VU EV ie are strings ofvariables and terminals and A 7gt w E R ie is a rule ofthe SENTENCE grammar then we say that uAv yields uwv written uAv gt uwv We may also say that uwv is directly derived from uAv using the rule A 7gt w 5 NOUN 7 PHRASEltVERB 7 PHRASE 5 OP 7 NOUNltVERB 7 PHRASE 5 ARTICLE NOUN VERB 7 PHRASE 5 a ltNOUNltVERB 7 PHRASE 5 a boy VERB 7 PHRASE 5 a boy CP 7 VERB 5 a boy VERB a boy sees ertsmcampmmmn 7 mm ernsatcampmmmn7p am Language Speci ed by G Derivation r G V7 371375 is a CFG the the language Specmed by j 7 We write u gt 2 if u 2 or ifa sequence j G orthe language ofG is a CFL u1u2uk e V u E exists for k 2 0 and ulgtu2gtgtukgtl 9 We may also say that u1u2 ukv is a derivation Ofv from ul ertsmcampmmmn 7amp11263 lensm Campmatmn7p was Important application More examples of CFGs Contextfree grammars are used as basis for compiler Consider the grammar design and implementation G3 S7 1717 5 1519 i 55 i 67 S 9 Contextfree grammars are used as specification mechanisms for 0 LG3 contains strings such as programming languages abab aaabbb aababb 1 Designers of compilers use such grammars to implement compiler s components such ascanners parsers and code generators Note if one think of a and b as and then we can see I The implementation of almost any programming language is that Hag is the language of 3 Strings of properly nested preceded by a contextfree grammar that specifies it parentheses L Limitsatcampmatmn 421w lensm Campmatlanrp 13m Example Derivation with G4 Arithmetic Expressions T 77 7 0 Consider the grammar G4 ETFaRE E whereRIs E T t E A ETlT TI 1 T T TFF ll ll a F a EH11 a a LG4 is the language of arithmetic expressions Figure 2 Derivation tree for aaa Limitsatcampmatmn 411563 lensm Campmatlan 411563 I 5 Design Techniques Many CFG are unions of simpler CFGs Hence the suggestion is to construct smaller simpler grammars first and then to join them into a larger grammar The mechanism of grammar combination consists of putting all their rules together and adding the new rules 3 S1 l Szl lSk where the variables S131 239 g k are the start variables of the individual grammars and S is a new variable mes m Cam Pmatmn 7 p a Designing CFGs As with the design of automata the design of CFGs requires creativity CFGs are even trickier to construct than finite automata because we are more accustomed to programming a machine than we are to specify programming languagesquot leltsm Campmatmn 411763 b 5 Second Design Technique Constructing a CFG for a regular language is easy if one can first construct a DFA for that language Conversion procedure 1 Make a variable Rz for each state 1239 of DFA Add the rule Rz gt aRj to the CFG if 6qia qj is a transition in the DFA Add the rule Rz gt e if qi is an accept state of the DFA If go is the start state ofthe DFA make R0 the start variable of the N As Theorem Every regular language is contextfree L mes m Cam Pmatmn 7 p 2cm Example Grammar Design 7 Design a grammar for the language 0 1 l n 2 0u 1 0 l n 2 0 1 Construct the grammar 31 a 0311 l eforthe language 0 1 l n 2 0 2 Construct the grammar SQ 1320 l eforthe language 1 0 l n 2 0 3 Put them together adding the rule S A 31 l 32 thus getting S a 81 l Sz 31 a 0311 l 6 Si 8 1320 l e lensm Campmatmnrp 19m Fourth Design Technique Third Design Technique In a complex language strings may contain certain Certain CFLs contain strings with two related substrings structures that appear recursively as are 0 and 1 in 0 1 l n 2 0 0 Example in arithmetic expressions any time the symbol 9 Example of relationship to recognize such a language a appear the entire parenthesized expression may a machine would need to remember an unbounded appear amount of info about one ofthe substrings 9 To achieve this effect one needs to place the variable A CFG that handles this situation uses a rule ofthe form generating the structure E in case of G4 in the location B a uRv which generates strings wherein the portion ofthe rule corresponding to where the structure may containing u s corresponds to the portion containing v s recursively appear as in E a E T Limits mew Pmatiari 7 2m Limnsat Campmatiari 7 21 m Amblgulty Example Appllcatlon is If a CFG generates the same string in several different j rCOrisiderthe CFG G SVB7aibiSH 313 l 6J3 A 3 l b73 j ways we say that the string is derived ambiguousy in The foowing are derivations with C that grammar S 3 aSB s 111333 3 aaSbBB 0 If a CFG generates some string ambiguously we say 3 313 H 333 3353 that the grammar is ambiguous 3 313 H 333 337 0 E I th rammar G whose rules are39 S 3 aSB A WSBB 3 WEB xamp e39 e g 5 39 which show that derivations in this grammar are quite complex E a E E l E gtk E l l a I When rewriting the string aaSBB we can considerfurther derivations of each of its symbols in isolation generate ambiguously some arithmetic expressions Derivationsfrom B are B 5 b3 5 bbB 5 bkilB 5 bk k 2 1 0 Therefore S gt 133 3 15 k 2 1 0 Hence LG anm l n g m Limits mew Pmatiari 7 2m Limits m Carri mam 7 2m Note The grammar G5 does not capture the usual precedence relations and so groups the before and vice versa In contrast the grammar G4 generates the same language but every generated string has a unique derivation tree Hence G5 is ambiguous and G4 is not ie G4 is unambiguous b b this at Cam initiation 7 p 25 Ambiguous expressions Figure 3 shows two different derivation trees for aaa E E E l E E I E i i i a a i i a a a a Figure 3 Two derivation trees for aaa m is m Cam initiation 7 p 25 Fixing rule application order Leftmost derivation a derivation of a string 10 in a grammar G is a leftmost derivation if at every step the leftmost nonterminal is replaced Rightmost derivation a derivation ofa string 10 in a grammar G is a rightmost derivation if at every step the rightmost nonterminal is replaced Note The leftmost and rightmost derivations ofa string 10 are unique so they are equivalent to the derivation tree L this at Cam initiation 7 in ma 7 Note r 1 When a grammar generates a string ambiguously it means that the string has two different derivation trees 9 Two different derivations however may produce the same derivation tree because they may differ in the order in which they replace nonterminals not in the rules they use 1 To concentrate on the structure of derivations we need to fix the order of rule application Limitsat Computation 7p 27 Chomsky Normal Form 0 It is often convenient to simplify CFG 1 One of the simplest and most useful simplified forms of CFG is called the Chomsky normal form 9 Another normal form usually used in algebraic specifications is Greibach normal form L l mus m Cam Pmatian 7 p 3mm Inherent Ambiguity Some CFL can have both ambiguous and unambiguous grammars b Some CFL however can be generated only by an ambiguous grammar b A CFL that can be generated only by ambiguous grammars is called inherently ambiguous b Example of inherently ambiguous language 0i1j2klz39jvjk le ns m cm Pmatian 7 p 29 Theorem 29 Any contextfree language is generated by a contextfree j grammar in Chomsky normal form Proof idea 1 Show that any grammar G can be converted into Chomsky normal form b Conversion procedure has several stages where the rules that violate Chomsky normal form conditions are replaced with equivalent rules that satisfy these conditions 5 Order oftransformations1 add a new start variable 2 eliminate all erules 3 eliminate unitrules 4 convert rules b Check that the obtained grammar define the same language as the initial mus m Cam Pmatian 7 p am De nition 7 A contextfree grammar G is in Chomsky normal form if every rule is of the form AgtBO A a where a is a terminal A B O are nonterminals and B C may not be the start variable Note the rule S a e where S is the start variable is not excluded lensat Campmatianrp 31 m Eliminate erules Proof Repeat Add a new start symbol S0 and the rule S0 A S where S 1 Eliminate the 6 rule A A e where A is notthe start symbol was the or39g39nal Start symbOI 2 For each occurrence of A on the T715 of a rule add a new rule with Note this Change guarantees that the start symbol does not that occurrence of A deleted Example TO delete A A e replace B A uAv by B A uAv 1 1w occur on the Th5 Of any rUIe replace R A uAvAw by B A uAvAw l uvAw l aAvw l uvw 90 Replace the rule B A A if it is present by B A A l 6 unless the rule B A 6 has not been previously eliminated until all 6 rules are eliminated L Ll L L mismcampmmn 7 am Ltmnsat Campmatmri 7 am Convert all remalnlng rules Remove unit rules rRe peat j rRe peat j 1 Replace a rule A A uluz uk k 2 3 where each ui 1g 2 g k is 1 Remove a unit rule A A B a variable or a terminalv by 2 For each rule B A u that appears add the rule A A u unless it A quot V411 A1 8 W421 A quot kiluk was a unit rule previously removed whereA A A L are new variables 1 2 k 2 until all unit rules are eliminated N If k 2 2 replace anyterminal ui with a new variable Uz and add the 399 1239 A Note u is a string of variables and terminals until no rules of the form A A ulug uk with k 2 3 remain L Ll L L mismcampmmn 7 35m Ltmnsat Campmatmri 7 35m Removing 6 rules Removing B 7 e Removing A 7 e amp S A B S ASA aB a B S e b D tilt U S ASAtaBtatSAtAStS BtS b tttt mus m Cam Pmatmn 7 p am Example CFG conversion Consider the grammar G6 whose rules are S 7 ASAraB A 7 BrS B 7 2 6 After first step of transformation we get S0 7 S S 7 ASAraB A 7 BrS B 7 2 6 m ns m Cam Pmatmn 7 p am More unit rules Removing A 7 B 30 S A B Removing A 7 S 30 S A B 7 ASA aB a SA AS 7 ASA aB a SA AS 7 SH 7 b 7 ASAtaBtatSAtAS 7 ASAtaBtatSAtAS 7 btASAtaBtatSAtAS 7 b 7 mus m Cam Pmatmn 7 p was Removing unit rule Removing S 7 S SO 7 S S 7 ASAraBrarSArAS A 7 BrS B 7 b Removing S0 7 S SO 7 ASAraBrarSArAS S 7 ASAraBrarSArAS A 7 BrS B 7 b 7 mnsm Campmatmn 7p as Note The conversion procedure produces several variables Ul along with several rules Ul gt a Converting the remaining rules SO AAllUBlalSAlAS 9 Since all these represent the same rule we may S AA1 l UB l a l SA l AS simplify the result using a single variable U and a single A A b AAl UB a SA AS ruleUaa A1 A SA U a a B a b L L Theorem r If CFG G is in Chomsky Normal Form then for any string 10 6 2 the length of the derivation Ofw is 2lwl i 1 lensm Computation in ma De nition 91 n A function f N sN where u is at least Ologn is b b b called space constructible ifthe function that maps the string 1 to the binaray representation of fn is computable in space Ofn For noninteger function fn we mean lfnl lf fn 0n we assume that we have a readonly input tape All commonly occurring functions that are at least 010gn are space constructible including 10g2n7n2 and 2 lelsm Campmatmnrp 215 22c131 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclal The University of Iowa Department of Computer Science Ch9 INTRACTABILITY lensatcampmatmnrp ms r Construction of D TM D runs in space Ofn but is not equivalent to any TMj M which uses ofn space D NA P9 0quot On input 102 Let n be the length Ofw Compute fn using space constructibility and mark off this much space If later stages ever attempt to use more reject Ifw is not of form M10 for some TM M accept Simulate M on 10 while counting the number of steps used in the simulation lfthe count ever exceeds 21 accept If M accepts reject If M rejects accept lelsm Campmatmnrp ms b b b b Theorem 93 7 Space hierarchy theorem For any space constructible function f N gt N a language A existsthat is decidable in space Ofn but not in space ofn Proof idea We need to find a TM D that runs in space Ofn but is not equivalent to any TM M which uses ofn space For any TM M which uses ofn space we construct D such that D and M behave differently on the input 10 where w M01k If M loops D must accept lensatcampmatmnrp ans 0 3 Corollary 97 PSPACE C EXPSPACE Uk SPACE2 k Problems in EXPSPACE i PSPACE are intractable because they require exponential space musm Campmatianrp ans 0 b Corollary 94 For any two functions f1 f2 N gt N f1n 0f2n and f2 is space constructible SPACEf1n C SPACEf2n Corollary 95 For 01 lt 02 n01 0n02 and n02 is space constructible so SPACEn01 C SPACEn02 Limnsatcampmmmnrp ans b b b b Theorem 910 Time hierarchy theorem For any time constructible function tN gt N a language A exists that is decidable in Otn but not in 0tnlogtn time Proof idea We need to find a TM D that runs in Otn but is not equivalent to any TM M which uses 0tnlog time For any TM M which uses otnlogtn time we construct D such that D and M behave differently on the input 10 where w M01k If M loops D must accept musm Campmatianrp ans b b De nition 98 A function t N gt N where tn is at least On log n is called time constructible ifthe function that maps the string 1 to the binaray representation oftn is computable in time Otn All commonly occurring functions that are at least On log n are time constructible including nIOgZ 71712 and 2 Limnsatcampmmmnrp ms I b b Corollary 91 1 For any two functions t1 t2 N gt N t1n 0t2nlogt2n and t2 is time constructible TIMEt1n C TIMEt2n Corollary 912 For 01 lt 02 n01 0n0210g 25201 and n02 is time constructible so TlMEn01 C TlMEn02 Corollary 913 P C EXPTIME Limilsatcampmmmn rpm15 TM whi Construction of D D runs in Otn but is not equivalent to any TM M ch uses otnlogtn time D On input 102 NA P9 0quot Let n be the length ofw Compute tn using time constructibility and store the value ltnlogtnl on the tape Ifw is not of form M10 for some TM M accept Simulate M on 10 while counting the number of steps used in the simulation lfthe count ever exceeds log accept If M accepts reject If M rejects accept Limnsatcampmmmnrp ans b b b Exponentiation Operation Let T REX x N gt REX be the exponentiation j operation R T k Rk Generalized regular expressions contains exponentiation operation EQREXT Q R i Q and R are equivalent generalized regular expressions Limilsatcampmmmn 411215 b b Regular Expressions Three base cases j u Q is a regular expression denoting the language Q I e is a regular expression denoting the language 6 3 For any a E E a is a regular expression denoting the language a Three recursive cases If n and M are regular expressions denoting languages L1 and L2 respectively then 0 Union r1 U m denotes L1 U L2 Concatenation rlrg denotes Lng 0 Star r f denotes L l Limnsat Campmatian 411115 Two NFAs are inequivalent NTM N can answer this question in linear space N quotOn input N1N2 where N1 and N2 are NFAs expressionsquot 1 Place a marker on each ofthe start states of N1 and N2 2 Repeat Step 3 2 11 12 times where 11 and 12 are the numbers of states in N1 and N2 00 Nondeterministically select an input symbol and change the positions ofthe markers on the states of N1 and N2 to simulate reading a symbol If at any point in Step 3 a marker was placed on an accept state of one of NFAs and not on any accept L state of the other NFA accept OthenNise reject Limitsmcampmmmn 421315 EX PSPA CECompleteness Definition 914 A language B is EXPSPAOEcomplete if it satisfies two conditions 1 B E EXPSPAOE 2 Every A E EXPSPAOE is polynomially time reducible to B Theorem 915 EQREXT is EXPSPACEcomplete Recall EQREXT Q R l Q and R are equivalent generalized regular expressions Limnsat Computation 411315 r EQREXT iS in EXPSPACE E quotOn input R1 R2 where R1 and R2 are generalized regular expressionsquot 1 Convert R1 and R2 to equivalent regular expressions B1 and B2 that use repetition insteand of exponentiation 2 Convert B1 and B2 to equivalent NFAs N1 and N2 using the conversion procedure given in the proof of Lemma 155 3 Use the deterministic version of algorithm N to determine whether N1 and N2 are equivalent Limnsat Computatioan 1515 Abstraction of Problems Data abstracted as a word in a given alphabet 2 alphabet a finite nonempty set of symbols 226 Limits of Computation 2 all the words of finite length built up using 2 Hamathang Conditions abstracted as a set of words called language 0 Any subset L g 2 is a formal language The University oflowa httpwwwcsumwaeduthhangclal Department ofComputerScience Unknown mpi0ity a Boolean variable true ifa word is the language no othenNIse Given w E 2 and L g 2 doesw E L L Limits m Campmatianrp M5 Limnsatcampmmmnrp m5 Formal De nition of Finite Automata Finite Automata WA finite automaton is a 5tuple Q 2 6 go F where j 7 The simplest computational model is called a nite state 9 Q is a finite set called the states maChme or a mte aummaton 0 2 is a finite set called the alphabet quot Regesetatl39 ns rap ica 6 Q x2 gt Q isthe transition function Tabular n 10 E Q is the start state also called Initial state Mathematical F g Q is the set of accept states also called the nal states Limits m Campmatianrp m5 Limnsatcampmmmnrp m5 Computation of a Finite Automaton Applications The automaton receives the input symbols one by one Finite automata are popular in parser construction of from left to right compilers 9 After reading each symbol M1 moves from one state to 9 Finite automata and their probabilistic counterparts another along the transition that has that symbol as its Markov chain are useful tools for pattern recognition label used in speech processing and optical character recognition 0 When M1 reads the last symbol of the input it produces 0 Markov chains have been used to model and predict the output accept if M1 is in an accept state or reject if price changes in financial applications M1 is not in an accept state lelsm Campmatmnrp m5 lensatcampmatmnrp ms Formal De nition of Acceptance Language of an Automaton 77 7 liLet M QE6q0 F be a finite automaton and lfL isthe set of all stringsthat a finite automaton M w 1102an be a string over 2 accepts we say that L is the language of the machine Then M acceptSw ifa sequence of states r0 r1 r7 exist M and wr39te MM L39 in Q such that the following hold 0 An automaton may accept several strings but it always recognizes only one language 0 If a machine accepts no strings it still recognizes one language namely the empty language Q h 1 T0qo N 602311241 T241170 01tttn71 3 Tu E F Condition 1 says where the machine starts bb Condition 2 says that the machine goes from state to state according to its transition function 6 b Condition 3 says when the machine accepts its input if it ends up in L an accept state lelsm Campmatmnrp M5 lensatcampmatmnrp ms Designing Finite Automata Regular Languages 0 Whether it be of automaton or artwork design is a i i We say that a finite automaton M recognizes the language creative process Consequently it cannot be reduced to L if L w l M accepts w a simple recipe or formula The approach Definition A language is called regularlanguage ifthere exists 1 Identify the finite pieces of information you need to a finite automaton that recognizes it solve the problem These are the states 3 Identify the condition alphabet to change from one state to another 1 Identify the start and final states 0 Add missing transitions Limitsmcampmmmn 7 ms Limnsatcampmatmnrp 9amp5 Regular Expressions Operations on Regular Languages if Three base cases j ii Let A and B be languages We define regular operations Q is a regular expression denoting the language Q union concatenation and star as follows e is a regular expression denoting the language 6 Uquoti quot A U B 95 t 5 6 AV 95 E B 0 For any a E E a is a regular expression denoting the c quot atequotati quot A O B 951 t1 6 A A y E B language a 1 Star A 11x2 xk l k 2 0 an E 141313 k2 Note Because any numberquot includes 0 e E A no matter 9 Three recursrve cases If n and M are regular what A is expressions denoting languages L1 and L2 respectively then 1 Union 71 U m denotes L1 U L2 Notation A denotes A o A Concatenation rlrg denotes Lng L 0 star r f denotes L f Limitsmcampmmmn 421MB lensm Computation in ms Closure under Complementation Closure under Intersection 0 Theorem That class of regular languages is closed under Theorem That class of regular languages is closed under complementation intersection 0 Proof For that we will first show that if M is a DFA that 9 Proof Use crossproduct construction of states recognizes a language B swapping the accept and nonaccept states in M yields a new DFA that recognizes the complement of B L ertsatcampmatmn 7 ms lensat Campmatmnrp ms Two ways to Introduce Nondeterminism Nondeterminism 0 More choices for the next state Zero one or many j 7 So far in our discussion every step ofa finite arrows may exit from each state automaton computation follows in a unique way from 9 A state may change to the next state without spending the preced39ng Step39 an input symbol etransitions We call this a deterministic computation In a nondeterministic computation choices may exist for the next state at any point Nondeterminism is a generalization of determinism hence every finite automaton is a nondeterministic finite automaton NFA 7 b b ertsatcampmatmn 421MB ertsat Computater 7 ms Tree Computation of NFA A way to think of a nondeterministic computation is as a tree of possibilities 0 The root ofthe tree corresponds to the start of the computation 0 Every branching point in the tree corresponds to a point in the computation at which the machine has multiple choices 0 The machine accepts if at least one of the computation branches ends in an accept state leltsmcampmmmn 7 1M5 Formal De nition of NFA 1 An NFA is a 5tuple Q7 267 F where bb 1 Q is a finite set called the states 3 E is a finite set called the alphabet n max mewww where 79Q is the power set on 9 10 E Q is the start state also called initial state 1 F g Q is the set of accept states also called the nal states In a DFA transition function is 6 Q X E gt Q notation For any alphabet E 26 E U 6 lensm Campmatmn 7 ms Computation by an NFA liLet N Q 26410 F be an NFA and w a string over 2 We say that N acceptsw ifw a1a2am 1139 6 26132 m and a sequence of states r0 r1 rm exists in Q such that 1 7 0 10 2 n1 E 6Ti7ai1f0ri 01777 7 1 3 rm 6 F 9 Condition 1 says the machine s starting state 5 Condition 2 says that state n1 is one ofthe allowable new states when N is in state m and reads 1H1 Note that 6m 1H1 is a set 5 Condition 3 says that the machine accepts the input if L the last state is in the accept state set mes m Cam Pmatmn 7 in ms b b b 55 Why NFA 7 Constructing NFA is sometimes easier than constructing DFA An NFA may be much smaller than a DFA that performs the same task Computation of NFA is usually more expensive than that of DFA Every NFA can be converted into an equivalent DFA NFA provides good introduction to nondeterminism in more powerful computational models lelsm Campmatmn 421MB A Property Equivalence of NFA and DFA Any NFA N can be converted to an equivalent NFA N that Theorem Every NFA automation has an equivalent DFA to has a single accept state recognize the same language Proof By construction Let N Q 26q0F be any NFA Then DFAs and NFAs recognize the same class of languages N omawn where This equivalence is both surprising and useful 1 Q Q U qa where qa Is a new state o It Is surprising because NFAs appears to have more powerthan 2 E E DFA so we might expect that NFA recognizes more languages 3 16 10 n It is useful because describing an NFA for a given language 4 sometimes is much easier than describing a DFA WM 54711 lfa 0rq F 6qaUqa7 lfaeanquF 5 F qa Questlon Appllcatlon of NFA lils the class of languages recognized by NFAs closed under 7 0 Now we use the NFA to show that collection of regular languages is closed under regular operations union concatenation and star Theorem 125 145 The class of regular languages is closed underthe union operation Theorem 126 147 The class of regular languages is closed under concatenation operation Theorem 149 The class of regular languages is closed under star operation complementation b b b L l L leltsatcampmatmn 7 Ms lensm Campmatlanrp ms Corollary 140 Equivalence of NFA and DFA A language is regular iff some NFA recognizes it The Formal Proof P f Let N Q 26410 F be the NFA recognizing the language r 39 A We construct the DFA M recognizing A quot If a language A 395 re 9 39z d by an NFA ther A IS 1 Before doing the full construction consider first the recognized by the DFA equwalent hence A Is regular easier case when N has no 6 transitions 9 If a language A is regular it means that it is recognized by a DFA But any DFA is also an NFA hence the Then we conS39derthe E trans39t39ons39 language is recognized by an NFA Notation For any R g Q define ER to be the collection of states that can be reached from R by going only along 6 transitions including the members of R themselves Formally ER RU q E Q l 371 6 R73 rk E Qn1 E 6m ewk q b lelismcampmmmn 7 2m lensm Computation in ms Question Why are we unsuccessful in finding polynomial time algorithms for some problems Possible answers 9 Perhaps such problems have as yet undiscovered polynomial time algorithm that rest on unknown principles 0 Some of such problems simply cannot be solved in polynomial time They may be intrinsically difficult L l leltsat Campmatmnrp 255 22c131 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclal The University of Iowa Department of Computer Science The Class NP lensatcampmmmnrp 155 Example Hamiltonian path problem j 0 A Hamiltonian path in a directed graph G is a path that goes through each node of G exactly once 0 Hamiltonian path problem consists of testing whether a directed Graph G contains a Hamiltonian path connecting two specified nods l HAMPATH ltGstgt l G is a directed graph with a Hamiltonian path from s to t L l leltsat Campmatmnrp was Why Complexity Theory r Complexities of many problems are linked The discovery ofa polynomial time algorithm for one such problem can be used to solve an entire class of problems lensatcampmmmnrp 355 Polynomial Veri ability A Hamiltonian path The HAMPATH problem has a feature called polynomial Figure 1 shows a graph that contains a Hamiltonian path veri ability which is important for understanding its between nodes 5 and t complexity If a Hamiltonian path in a graph G is discovered somehow we could easily convince someone else of its existence simply by presenting it s t That is verifying the existence of a Hamiltonian graph may be much easier than determining its existence Figure 1 A Hamiltonian path L Lmutsat Campmatmnrp 555 Ltmnsatcampmatmnrp 555 Note Another example 77 Some problems may not be polynomially verifiable For Another example of polynomial verifiable problem is example HAMPATH the complement of HAMPATH is number compositness nOt pOIYnom39al t39me Ver39f39able A natural number is composite if it is the product oftwo integers greater than 1 COMPOSITES I l I ENAI pqpq EA4911 gt1 7 Rationale Even if we could determine that a graph did not have a Hamilto nian path we don t known a way forverifying its nonexistence without using Although we don t know a polynomial time algorithm for de the same exponential time algorithm that determined its nonexistence ciding this problems we can easily verify that a number x is composite all that is needed is a divisor of x Lmutsat Campmatmnrp 555 Ltmnsatcampmatmnrp 755 Observations Veri er l A verifier uses additional information represented by c in Verifier s A verifier for a language A is an algorithm V where definition A w l V accepts ltwcgt for some string c 0 This info is called a certi cate or proof of membership Note 0 For polynomial verifiersthe certificate has a polynomial length in the Time of the verifier is measured only in terms of length length 0h Ofw A polynomial time verifier runs in polynomial time 0 Examples the certificate for Cstgt e HAMPATH is a Hamiltonian path between s and t the certificate for z e COMPOSITES Is a A language A is polynomially veri able if it has a d39V39SOrP Of I polynomial time verifier in the length Ofw L l l Limitsmcampmmmn 7 was Limnsatcampmatmnrp 955 A NTM deciding HAMPAT H The Class NP rN quotOn input am where G is direct graph with nodes at W rNP is the class of languages that have polynomial time j 1 Write a list of m numbers 101102 pm where m is the number of ver39f39ers nodes in C Each number is nondeterministically selected between 1 Note and m I The term NP comes from nondeterministic polynomial time and is 239 Cheek for repet39t39ons quot1 the St any are found eed derived from an alternative characterization using nondeterministic 3 Check whether 5 p1 and t pm If eitherfails reject polynomial time Turing machines 4 For each 2 1 g 2 g m check whether plmill is an edge of C If 9 NP class is important because it contains many problems of practical any are not reject Otherwise acceptquot interest 0 HAMPATH COMPOSITES e NP Note that COMPOSITES e P but proving it is more difficult L l l Limitsmcampmmmn 411255 Limnsm Campmatian 411155 Proof Theorem 720 A e NP gt A is decidable by a polynomial time NTM A language is in NP iff it is decided by some Assume that V is polynomial time verifier deciding A in time 711 The NTM nondeterminiStiC pelynomial time Turing maChine39 NV equivalent to V works as follows Proofidea NV quotOn input w of length n 0 We show how to convert a polynomial time verifier to an equivalent 1 Nondeterministically select a string 6 of length at most 711 pelynomial time NTM and Viceversa39 2 Run V on input ltw Cgt l The verifier simulates the NTM by using the accepting branches as certificates 3 If V accepts accept if V rejects rejectsquot L l l Limitsmcampmatian 421355 Limitsm Campmatian 411355 Class NTIMEtn Proof continuation T j VA The nondeterministic time complexity class NTIMEtn is 7 ssume that A is decided by a polynomial time NTM N and construct a defined by polynomial verifier VN that decides A NTIMEtn L l L is a language decide by an Otn NTM VN quoton lnPUt 11176 Where w and C are Strings 39 quota NP Ur NTIMW 139 ESEESZZQSEEEEZEZEZiTE 21ZZZZELZQSZZSZSSZWO Of Proof obvious from previous considerations compilation Simu39a onl 2 lfthis branch of N s computation accepts accept otherwise reject L l l Limitsmcampmatian 411555 Limnsat Campmatianrp 1555 Undlrected graphs and cllques Observations l A clique in an undirected graph is a subgraph wherein every two I The class NP is insensitive to the choice of reasonable nodes are connected by an edge nondeterministic computational model because all such models are 0 A kclique is a clique containing k nodes Figure 2 illustrates a graph pelynomial eqUivalent with a 5 clique 0 When describing and analyzing nondeterministic polynomial time algorithm we follow the notational conventions set up for deterministic Clique problem polynomial time algorithms b Each stage of a nondeterministic polynomial time algorithm must have an obvious implementation in nondeterministic polynomial time on a reasonable nondeterministic computational model CLIQUE 0 k l G is an undirected graph with a kclique b Algorithm analysis shows that every branch uses at most polynomially many stages L Ll L L Limitsmcampmatmn 7 1555 leism Campmatlan 411755 Theorem 724 Example graph with a clique T 77 7 CLIQUE E NP Proof idea the clique is the certificate The following is a verifier V for CLIQUE V quotOn input ltltGkgtc 1 Test whether 6 is a set of k nodes in G 2 Test whether G contains all edges connecting nodes in c Figure 2 A graph with a 5clique 3 If both pass accept otherwise rejectquot L Ll L L Limitsmcampmatmn 7 zuss lensm Campmatlanrp 1955 SUBSETSUM Problem Alternative proof A collection of k integers 1112 xk and a target numbert If one prefers to think in terms of polynomial time NTM one are given We want to determine whether this collection can construct the following NTM N that decides CLIQUE contains a subcollection that adds up to t N quotOn input lt07 kgt where G is undirected graph SUBSET SUM ltStgt l S 11zzzk and for some 0 ytiyziuwyz Q SW6 haVe ZZZyi t Nondeterministically select a subset C of k nodes of G 2 Test whether all nodes in c are connected and whether G contains all Example lt41116212725gt E SUBSEFSUM because 4 21 25 edges connecting nodes in 0 Note 1112xk and y1y2 yl may be multisets 339 39fyes accept othem39se rejects Alternatlve proof Theorem 725 W rSUBSETSUM E NP j Proofidea the subset is the certificate liWe can also prove this theorem given the NTM N that decides SUBSET SUM N quotOn input St The following is a verifier V for SUBSET SUM 1 Nondeterministically select a subset c of numbers in S V quotOn input lt37 We 2 Test whether 6 is a collection of numbers that sum to t 1 Test whether 0 is collection of numbers that sum to t 3 lfthe teSt passes accept OthelWisei ref601quot 2 Test whether S contains all the numbers in C 3 If both pass accept otherwise rejectquot L 7 7 7 Limits atcam Pmatiari 7 was Limnsatcampmatianrp 2355 The P versus NP question P the class of languages for which membership can be decided quickly NP the class of languages for which membership can be veri ed quickly Question is PNP This is one ofthe greatest unsolved problems in theoretical computer science and contemporary mathematics mm m Cam Pmatlan 7 p 2555 I b b b Observations It seems that verifying that something is not present is more difficult that that it is present Hence CLIQUE and SUBSET 7 SUM are not obviously members of NP A separate complexity class denoted coNP contains languages that are complements of languages in NP class We don t know whether NP is different from coNP lensat Campmatlan 7 2555 Advance on the P versus NP 0 Certain problems in NP have their individual complexity related to that of the entire class Stephen Cook and Leonid Levin 19705 If a polynomial time algorithm exists for any of these problems all problems in NP class would be polynomial time solvable These problems are called NPcomplete and the phenomenon of NPcompleteness is important for both theoretical and practical reasons b b mm m Cam Pmatlan 7 p was b b b b Observations If P is equal to NP then any polynomial verifiable problem would be polynomially decidable 7 Most researchers believe that P3 NP because people have invested enormous effort to find polynomial time algorithms for some problems in NP without success A proofthat P3 NP would mean that no fast algorithm exists to replace bruteforce search for some problems This may be beyond scientific reach Best method known for solving problems in NP deterministically is based on deterministic simulation of NTM which is exponential ie NP g EXPTIME Uk TIME2 I But we don t know whether NP is contained in a smaller determionistic time complexity class lensat Campmatlan 7 2755 I 5 Practical Importance The phenomenon of NPcompleteness may prevent wasting time searching for a nonexistent polynomial time algorithm to solve a particular problem Even though we may not have the necessary mathematics to prove that the problem is unsolvable in polynomial time showing that it is NPcomplete will suffice because we believe that P7 NP mm m Cam Putatan 7 p arr55 I I b Theoretical Importance Research trying to show that PNP may focus on an NPcomplete problem If any problem in NP requires more than polynomial time an NPcomplete does Research trying to show that PNP only need to find a polynomial time algorithm for one NPcomplete problem m ns m cm Putatan 7 p 2955 r SATEPlffPNP CookLevin Theorem 7 Proof idea Use polynomial time reducibility method mm m Cam Putatan 7 p 3255 b I 5 Example NPcomplete problem A Boolean formula is an expression involving Boolean variables and operations For example ltIgt i y v x 2 is a Boolean formula A Boolean formula is satisfiable if some assignments of 1 and 0 true and false to its variables makes the formula evaluates to 1 For example the assignment as 0y 12 0 makes ltIgt evaluate to 1 The satisfiability problem SAT is to test whether a Boolean formula is satisfied ie SAT l P is a satisfiable boolean formula lensm imputatan 7p 3155 Polynomial time computability Comments on reducibility 1 When problem A reduces to problem B a solution to B can be used to solve A 0 Polynomial time reducibility is a reducibility method that takes the efficiency of computation into account 0 When problem A is efficiently reducible to problem B an efficient solution to B can be used to solve A efficiently A function f 2 gt 2 is a polynomial time computable function if some polynomial time TM M exists that halts with just fw on its tape when started on any input 10 Limilsmcampmmmn 7 was mnsm Campmatian 7 3355 Observations Polynomial time reducibility T 7 7 0 A polynomial time reduction of A to B provides an A language A is polynomial time mapping reducible or efficient way of converting membership testing in A to polynomial time reducible to a language B written A p B if membership testing in B a polynomial computable function f 2 gt 2 exists where 0 To test whether 10 E A we use the reduction f to map 10 for every w E 2 w E A gt u E B Into w and teSt w E 3 Note f is called the polynomial time reduction of A to B 0 If language A is polynomial reducible to language B which has a polynomial time solution then A has a polynomial time solution Limilsmcampmmmn 7 3555 mnsm Campmatianrp 3555 b b b Conjunctive Normal Form Literal a Boolean variable or a negated Boolean variable Examples 1 and i are literals Clause several literals connected with V Example 11 V I V f3 V I4 is a clause Conjunctive normal form a Boolean formula which is a conjunction of several clauses ie connected with A Example 11 V I V f3 V 14 A 13 V f5 V 16 A 13 V is is a cnfformula 3CNFformula a CNFformula where each clause has three literals Example 11 V I V f3 A 13 V f5 A 13 V 16 V 14 A 14 V 15 V 16 Limits m Cam Pmatiari 7 p 3555 Theorem 731 lngpBandBePthenAeP Proof let M be a polynomial time algorithm deciding B and f be a polynomial time reduction from A to B Then the algorithm N is a polynomial time decider of A N quotOn lnputw 1 Compute fw 2 Run M on input fw and output whatever M outputsquot Note Since composition of two polynomial is polynomial N is a polynomial time algorithm Limnsat Computation 7p 3755 b b b Proof Idea The polynomial time reduction f that we demonstrate from 3SAT to j CLIQUE converts formulas to graphs In the constructed graphs cliques of a specialized size correspond to satisfying assignments of the formula Structures within the graph are designed to mimic the behavior of the variables and clauses Limits m Cam Pmatiari 7 p was r BSAT Problem j 3SAT is a special case of the SAT problem where the Boolean formula is a 3cnf 7 formula That is 3SAT ltltIgtgt i lt1 is a satisfiable 3cnf formula Theorem 732 3SAT problem is polynomial time reducible to CLIQUE om its m Cam Pmatiari 7 p 3955 Nodes of G b Nodes in G are organized in k groups of three nodes each called the triplets t17t2 t t t tk b Each triplet correspond to one of the clauses in lt1 and each node in the triplet corresponds to a literal in the associated clause b Label each node of G with its corresponding literal in lt1 L A Limits m Cam Pmatiari 7 p was Proof Let P be a formula with k clauses lt1a1VblVc1Aa2VszcszMakachk The reduction f generates the string G k where G is a undirected graph Limnsat Campmatianrp 6155 Example BSAT reduction to graphs T 7 3SAT formula lt1 11 V 11 V 12 A 11 V I V f2 A 11 V 12 V 12 in transformed in the graph in Figure 3 Figure 3 L A Limits m Cam Pmatiari 7 p was r Edges of G Edges of G connect all but two types of pairs of nodes in G I No edge is present between the nodes of the same triplet 7 0 No edge is present between two nodes with contradictory labels such as 12 and f2 Limnsat Campmatian 7 was Proof continuation A kclique in G implies lt1 is satisfiable Suppose G has a kclique I 9 b No two of the clique nodes can occur in the same triplet because nodes in the same triplet are not connected Therefore each the ktriplets contains contains one ofthe kclique nodes Assign truth value to the variables of lt1 so that each literal labeling a clique node is made true This is possible because two nodes with contradictory labels are not connected This assignment satisfies the formula lt1 Since each node corresponds to a clause that has a true value in it the clause is true since classes are connected by A the formula is true leis m Cam Putatan 7 p was Why this construction works P is satisfiable iff G has a kclique Proof 3SATgt CLIQUE Suppose that lt1 has a satisfying assignment I I b b At least one literal is true in every clause required by V In each tripled of G we select one node corresponding to a true literal in the satisfying assignment If more literals are true in some clause we select the true literal arbitrarily The nodesjust selected form a kclique number of nodes is k there are k clauses in lt1 and each pair of selected nodes are joined by construction Selected node are not from the same triplet by construction they could not have contradictory labels because otherwise the associated labels would be both true in the satisfying assignment Hence G contains a kclique lensm imputatan 7 was A language B is NPcomplete if it satisfies two conditions 1 2 De nition of NPCompleteness 7 B E NP Every A E NP is polynomial time reducible to B leis m Cam Putatan 7 p was b b 0 Conclusions If CLIQUE is solvable in polynomial time so is 3SAT j Polynomial time reducibility allows us to link these two very different problems Similar link may be made among other problems leism imputatan 7 was lfB is NPcomplete and B p O for O E NP then C is Theorem 736 NPcomplete Proof Since 0 e NP we only need to showthat every A e NP is polyn omial time reducible to C 0 D b Since B is NPcomplete A is polynomial time reducible to B Since B is polynomial time reducible to C A is polynomial time reducible to C by first reducing it to B and then reducing its image to 0 Hence every language in NP is polynomial time reducible to C rm m Cam Pmatian 7 p sci55 Theorem 735 lfB is NPcomplete and B E P then P NP Proof this follows directly from the definition completeness of NP Limnsm Computation 7 was Ni 0 Proof SAT 6 NP a nondeterministic polynomial time machine can guess j an assignment to the variables of a given formula lt1 and accept if assignment satisfies lt1 Let A e NP showthat A is polynomial time reducible to SAT For a NTM N that decides A in 71 time for some constant k construct a formula lt1 that simulates N Construction oflt1gt1 based on organizing the computation performed by N into an 71 x 71 tableau as seen in Figure 4 rm m Cam Pmatian 7 in 5255 The CookLevin Theorem r Theorem 737 SAT is NPcomplete Proofidea I Show that SAT 6 NP which is easy 7 I Show that any language A e NP is polynomial time reducible to SAT 0 The reduction ofA takes a string w and produces a Boolean formula lt1 that simulates the NTM N that decides A operating on w b lfN accepts lt1 has a satisfying assignmentthat corresponds to that computation if N doesn t accept no assignment satisfies lt1 Hence w e A iff lt1 is satisfiable Limnsat Computation 7 5155 TableauNw Con gurations tableau of N a Every accepting tableau for N and w correspond to an accepting computation branch ofN on w 0 Problem of determining whether N accepts w is equivalent to the problem of determining whether an accepting tableau for N and w exists first configuration second configuration window nk th configuration Figure 42 A tableau is an 71 x 71 table of configurations Observations 1 Each configuration starts and ends with a symbol L LQ A tableau is accepting if any of its rows is an accepting configuration 7 leltsatcampmatmn 75 5555 um As at Cam 551515575 5355 Assignmenttableau correspondence Polynomial time f A gt SAT 77 7 b The assignment turns on exactly one variable for each cell using the following constructs On input w f produces ltIgtw 0 Variables of Dw Let N Q7 EF6q0qaq and C Q U 1quot U 1 at least one variablethat is associated with a cell is on by Vigor For each 1 g z j g 71 A s e C we have a variable I in lt1gtw 2 no more than one symbol in each cell by Asgeogggmvm 1 Cells of the 71k2 entries of a tableau is called a cell Vs e 0 Thus any satisfying assignment specifies one symbol in each cell by 231 1 if ceulivjl 5 0 Formula ltIgtw is ltIgtw chad A chum A chum A chum been A19ng VSEC Iig e A AstECIiJSS V L A L 7 leltsatcampmatmn 75 5555 um As at Cam 551515575 5555 Legal window A 2 x 3 window of cells is legal if that window does not violate the actions specified by N s transition function To explain considerthe transitions 601112qzicyLquyayRH Examples of legal Windows for this machine are In Figure 5 a b c H EH nan d a nun Ell III Figure 5 Examples of legal windows Limits m Cam Pmatian 7 in 5555 An accepting tableau is speCi ed Estarti Emovei Paccept I chum ensures that the first row ofthe tableau is the starting configuration of N on w by the equality Qstart Il1Il2quzl3w1A Iln3wntttA11nk71l 1Axlnk chum guarantees that an accepting configuration occurs in the tableau by placing qa in one ofthe cells by chum Vlgmgnk 123 chmm guarantees that each row of the tableau correspond to a configuration that legally follows the preceding row s configuration according the N s transition rules m its m cm Pmatian 7 in 5755 Illegal windows Figure 6 shows illegal windows of N tiny I l BEE HE E Figure 62 Examples ofillegal windows 7 I a is illegal because the central symbol on the top can t be changed because it has no adjacent state 9 b is illegal because the transition specifies that 12 get changed to c not to a 0 c is illegal because two states appear in the bottom row Limits m Cam Pmatian 7 p sci55 b b b b b Comments V ndows a and b are legals because the transition allows N to move this way 7 V ndow c could be either illegal or illegal because ql appears to the right side of the top row and we don t know what symbol is the head over V ndow d is legal because top and bottom are identical what could happen ifthe head weren t adjacent to the location of the window V ndow e is legal because state ql reading a 12 might have been immediately to the right of the top row and would have moved to the left V ndow f is legal because state ql might have been immediately to the left ofthe top row changing b to c and moving left m its m cm Pmatian 7 in 5955 Construction of Dmove Claim Emma stipulates that all windows in the table are legal lfthe top row ofthe tableau is the start configuration and every every window is legal then each row is a configuration that legally follows the configuration represented by the preceding row 0 Each windows contain six cells which may be set in a fixed number of ways to yield a legal window chmm says that the setting ofthose six cells is done this way by Dome Algijgnkwind0wiv is 169111 Proof show the claim for any two adjacent configurations 5 Replace windowlz j is legal with the following formula where a1a2a3a4 15116 are the contents of the six cells Values legaz irlm A 1231422 A 12 an A 241171 A Ii1jas A Ii1j1ae L l l leltsmcampmmmn 7 5255 lensm Campmatmn 7 was BSAT is NP Complete Complexity of the reduction r Proof provide a polynomial time reduction from SAT to 3SAT j 7 Tableau is 71k x 71k and thus contains 71 cells each cell has lCl l Transform rst DSAT into cnf variables associated with it where 1 depends only on N Hence total number of variables is 001 7 b 1 Represent each component ofthe cnf 11 V 12 V V an by n2 Clauses 11 V 12 V 21 A 51 V 13 V 22 A t t t znlg V anzl V an b Estimating the size of four components of lt1 chad is a fixed fragment of lt1 so its size is fixed and is 001 chum has the size 0nk chmm and chum have sizes 001 Hence total size of lt1 is mathcalOmZk ie size of lt1 is polynomial in n b Each component of lt1 can be produced in polynomial time Therefore we conclude that we can construct a reduction that produces lt1 from N in polynomial time This concludes the proof of CookLevin Theorem showing that SAT is NPcomplete L l l leltsmcampmmmn 7 was lensm Campmatmn 7 5355 Other NPcomplete languages To show that A is NPcomplete provide a polynomial time re duction from A to 3SAT or to other NPcomplete languages m ns m Cam Pmalian 7 p 5555 101 Approximation Algorithms An algorithm is TM decider 9 Formal languages represent decision problems most of 226 Limits of Computation which can be solved by Turing machines Hantathang Some problems look for minimum or maXImum values m WWW CS mm eduthhan km called optimization problems most of which can be p V V V g computed by Turing machines The University o owa Finding an optimal value may be too expensive a Department ofComputer Science nearly optimal may be good enough and easier to find Such Turing machines are called approximate algorithms Ch39m ADVANCED TOPICS Proof of Theorem 101 Vertex Cover Problem liTheorem101 There is a polynomial time algorithm that j 7 Decision version VertexCover G k l G V E an produces a vertex cover of G that is no more than twice as undirected graph k an integer G has a vertex cover large as a smallest vertex cover whose size is no more than k 0 Optimization version Given G find a vertex cover of A On input G where G is an undirected graph 1 Repeat the following until all edges in G have a marked endpoint 2 Find an edge in G that have no marked endpoints 3 Mark the two endpoints ofthat edge 4 Output all marked nodes minimum size in G b Theorem 744 VertexCover is N Pcomplete Theorem1o1 There is a polynomial time algorithm that produces a vertex cover of G that is no more than twice as large as a smallest vertex cover b Algorithm A satisfies the conditions in Theorem 101 leltsm Campmatmnrp MM lensalcampmmmnrp 3m b bb MaxCut Decision version MaxCut G k l G V E an undirected graph k an integer G has a cut S T such that E m S x Tl 2 k Optimization version Given G find a cut whose cut edges are maximum in G Theorem MaxCut is NPcomplete Note The MinCut problem is in P lellsm Campmalmnrp 5m kOptimal 1 Minimization problem An approximation algorithm is koptimal if it always finds a solution that is not more than k times the size ofthe optimal Maximization problem An approximation algorithm is koptimal if it always finds a solution that is at least 1k times the size ofthe optimal lensatcampmmmnrp 5m L b b 102 Probabilistic Algorithms A probabilistic algorithm is an algorithm designed to use the outcome ofa random process Definition 103 A probabilistic Turing machine M is a type of nondeterministic Turing machine in which each nondeterministic step is called a coinflip step and has two legal next moves We assign probability to each branch b of M s computation on input 10 as follows Define the probability of branch b to be Prlb 2 where k is the number of coinflip steps that occur on branch b Define the probability that M accepts w to be PrM accepts w Z Prb b is an accepting branphwmmwjm r T a Theorem 102 7 heorem1o2 There is a polynomial time algorithm 2optimal pproximate algorithm for MaxCut B On input G where G V E is an undirected graph NA 00 LetSTV lf moving a single node either from S to T or from T to S increase the size of the cut make that move and repeat this stage If no such node exists output S T Algorithm B satisfies the conditions in Theorem 102 lensatcampmmmnrp ml Lemma 105 Let 6 be a fixed constant strictly between 0 and 05 Then for any polynomial pn a probabilistic polynomial time Turing machine M1 that operates with error probability 6 has an equivalent probabilistic polynomial time Turing machine M2 that operates with an error probability of 2 10 mus m Cam Pmatian 7 in mm The Class BPP b b PrM rejects w 1 7 PrM accepts w b probability 5 if 1 w E A implies PrM accepts w 2 1 e and 2 u g A implies PrM rejects w 2 1 e b machines with an error probability of 13 PrM accepts w Z Prb7 b is an accepting branch For 0 S e lt 05 we say M recognizes language Awith error Definition 104 BPP is the class of languages that are recognized by probabilistic polynomial time Turing Limnsatcampmmmnrp am Some Lemmas 7 Suppose06elt12 1 E1ES14 2 6176 S 617 6 3 Ifwc2kw gt0 then ew1iec ek1iek 4 210 2 mus m Cam Pmatian 7 in mi Lemma 105 r Let 6 be a fixed constant strictly between 0 and 05 Then for any polynomial pn a probabilistic polynomial time Turing machine M1 that operates with error probability 6 has an equivalent probabilistic polynomial time Turing machine M2 that operates with an error probability of TMquot Proof Given TM M1 with error probability 6 lt 12 and a polynomial pn we construct a TM M2 that recognizes LM1 with an error probability of 210W M2 On input as 1 Calculate k pna where a log24e1i e 2 Run 2k independent simulations of M1 on input as 3 If most runs of M1 accept then accept othenNise reject 7 le SDVCDNPMMlDHP11 1 For We Proof of Lemma 105 Pr M2 outputs incorrectly on input ac 461 7 6k TM l l choose k 2 pltngtlog24e1 6 Limits m Cam Pmatian 7 in am Proof of Lemma 105 Pr M2 outputs incorrectly on input ac Pr M1 outputs on ac incorrectly 10 times and correctly 0 times Wherew 0 21910 gt c kil 2k 00 c6w17 EIC where ex Pr M1 outputs incorrectly on ac 25 lt25gtltegtwlt17 egtc S s k ltzfgtltegtklt1eegtk lt 5 lt25gtgtltegtklt1eegtk 202 gtgtltegtklt1egtk 22kgtltegtk 7egtk Limnsat Campmatianrp 13m b bb b Fermat Test Fermat s Little Theorem pr is prime and j a E Z 1 2 p i 1 then 03071 E 1 mod p FermatTest If an 1 7 1 mod n then n is not a prime PSEUDOPRIME On input n 1 Select a1a2 ak randomly in 2 2 Compute a mod n for each 239 3 If one ofthe computed values in step 2 is not 1 reject otherwise accept Example n 6 a1 2 26 1 32 and 32 mod 6 2 Limits m Cam Pmatian 7 in 1561 b bb b Example Primality Testing 7 Testing if a number is prime has been extensively studied There exists a complex polynomial time algorithm We present a practical approximation algorithm for this problem Some concepts I TWO numbers I and y are equivalent modulo p z E y mod p ifz mod p y mod p All the remainders byp is 2 012p 71 Fermat s Little Theorem pr is prime and a E Z 12 p 71 then 17 1 E 1 mod p b b Limnsat Campmatian 4115M b b b Korselt s Criterion Theorem Korselt 1899 A positive composite integer n is a Carmicheal number if and only if n is squarefree and for all prime divisors p of n p i 1 divides n 71ie p 7 1 1 n 7 1 EX 561 3111721560101560and161560 Theorem If n is neither prime nor Carmicheal number then there exist at least n i 12 as in Z71 such that an 1 7 1 mod n PSEUDOPRIME s error probability is 2 71 for pseudoprimes primes Carmicheal numbers this at Cam pmattan 7 218161 b b b Carmichael Numbers Some composite numbers n pass Fermat Test for any a where gcdna 1 Such numbers are called Carmichael numbers The first three Carmichael numbers are 561 1105 1729 Let Cn denote the number of Carmicheal numbers less than or equal to n 239 13141516171819110111 C10i 117116143110512551646115471360 5 11m As at Cam pmatmnrp 17m b b b b Squareroot Test 7 A number x E z is said to be a square root of1 modulo 711fo E1 mod 71 Lemma For any prime p it has only two square roots of 1 1 and p i 1 EX1 Four square roots of1 modulo 21 are 120 8 13 EX2 One square root of1 modulo Carmicheal number 561 is 67 672 4489 8 561 1 Squareroot Test lfac is a square root ofone modulo n x 1 and x e n i 1 then n is composite this at Cam pmattan 7 p 2mm Fermat Test on Carmicheal Numbers m X bbbbbbb 56131117 If gcd561a 3 11 then 6560 528 mod 561 gcd561a 3 17 then 1560 408 mod 561 gcd561a 11 17 then 6560 18 mod 561 gcd561 a 3 then 6560 375 mod 561 gcd561a 11 then 1560 154 mod 561 gcd561a 17 then 6560 34 mod 561 for other a 1560 1 mod 561 320 cases 7 11m As at Cam pmatmnrp 19m Squareroot Test Squareroot Test n Squareroot Test Ifx is a square root ofone modulo n Squareroot Test Ifx is a square root of one modulo n x o4 1 and x n i 1 then n is composite x 1 and x n i 1 then n is composite l SQUAREROOTTEST On 171 where 17171 E 1 mod n I SQUAREROOTTEST On 171 where anTl E 1 mod n 1 Compute h and s such that n 71 2hs where h 2 1 1 Compute h and s such that n i 1 2hs where h 2 1 and s is odd and s is odd 2 Let 950 a5 mod 71 If 950 1then accept 2 Let 950 a5 mod n 3 For from 1 to h repeat the following 3 For from 1 to h repeat the following 4 xj 11 mod n 4 xj 11 mod n 5 If M n 71then accept 5 If M 1 and acj1 y 1 and acj1 y n 7 1 reject 6 If acj 1 then reject 6 If no rejects in step 5 acceptquot 7 If no rejects in step 5 acceptquot LWh What s its time complexity at s its time complexity 7 i Squareroot Test 71 105 Squareroot Test 71 15 T 77 7 There are 16 values in Z1455 such that 1104 E 1 mod 105 1 8 13 22 There are fourvalues in ng such that 114 E 1 mod 15 1 14 4 11 b b 29 34 41 43 62 64 71 76 83 9297 104 they are square roots of1 modulo 15 0 Of them eight are square roots of 1 modulo 105 1 29 34 41 64 9 14 2 7 hence h 1 and s 7 71 76 10439 J Fora4 104734 mod 15 I 1042313 henceh3ands 13 11 16 42 1621 mod 15 D Fora8 1081338 mod 105 I Fora11 10117311 mod 15 zlzg8264 mod 105 zlzg11221 mod 15 12 1 642 E 1 mod 105 1 Conclusion For 14 numbers in Zng Fermat Test will succeed 10times 0 Conclusion For 104 numbers in Z1455 Fermat Testwill succeed 88 and Square Root Test will succeed 2 times The success rate is times and Square Root Test will succeed 14 times The success rate 1214 is 102104 L l 1 1m atcam Pmatian 7 2w lensm Computation 7 23m Squareroot Test 71 221 b There are 16 values in Z2431 such that am 21 mod 221 1 1821 38 47 64 86 103 118 135 157 174 183 200 203 220 Of them four are square roots of 1 modulo 221 1 103 118 220 0 220 22 55 hence h 2 and s 55 b b For a 211O 2155 E 200 mod 221 11 1 2002 E 220 mod 221 12 1 2202 E 1 mod 221 Since 11 221 e 1 the squareroot test failed There are six such cases 1 21 47 174 200 220 Conclusion For 220 numbers in Z331 Fermat Testwill succeed 204 times and Square Root Test will succeed 10 times The success rate is 214220 b L 1m m Cam Pmatiari e p 25141 Another Example 71 561 There are 320 values in 25 such that 1560 E 1 mod 561 Of them eight are square roots of 1 modulo 105 560 24 35 hence h 4 and s 35 Fora 210 285 E 263 mod 561 1 10 12 1 1662 E 67 mod 561 3 1 672 E 1 mod 561 Fora 510 585 E 23 mod 561 11 1g 232 E 529 mod 561 12 1 5292 E 463 mod 561 13 1 4632 E 67 mod 561 14 1 672 E 1 mod 561 Conclusion For 560 numbers in Z521 Fermat Testwill succeed 240 times and Square Root Test will succeed 318 times The success 7 rate is 558560 on As at Cam Pmatiari e p 25141 Combine Fermat and Squareroot Tests rM PRIME On input n where n is odd 1 Select 1112 ak randomly in 2 2 For each 139 from 1 to k illerRabin s Algorithm 3 Compute a mod n and reject if the value is not 1 4 Call SQUAREROOTTESTW n if it rejects reject 5 All tests have passed at this point so acceptquot Theorem If k 1 the error probability of PRIME is at most In general it is 4 11 LLet PRIMES n l n is a prime number in binary Theorem 109 PRIMES E BPP 7 1m m Cam Pmatiari e p 25141 b b b Squareroot Test LetAaEZlaquotTlE1modnandmlAl j The best theoretic result says that SQUAREROOTTEST will succeed at least m2 times for numbers in A The experimental results show that SQUAREROOTTEST will succeed m E 2 times in many cases Limitsat Computation 7 27m I b b 106 Cryptography Cryptography is a much older field area than computer science Modern cryptography tools use computers and many areas of computer science need cryptographic protection 1 Passwords protection war on hikers Secure networks online business and banking 1 Digital signatures 3 Evoting Complexity theory provides a way to gain evidence for a secret code s security because we know in complexity theory which functions are easy and which are hard to compute mus m Cam Pmatian 7 p sum b De nition 1010 RP is the class of languages that are recognized by probabilistic polynomial time Turing machines where inputs in the language are accepted with a probability of at least and inputs not in the language are rejected with a probability of 1 Let COMPOSITES n l n is a composite number in binary Then COMPOSITES 6 RP Limnsm Campmatian 7 29m b b b b OneWay Functions Formal A function f 2 gt 2 is lengthpreserving if lwl A onetoone lengthpreserving function is called a permutation Suppose a probabilistic Turing machine M computes a probabilistic function fM 2 gt 2 or simply fM 2 gt 2 Define the probability that Mw x to be PrMw ac Z Prb7 b is a branch where M halts in accept state with x on the tape for input 10 Since M may sometimes fail to accept an input 10 so 2 PrMw x S 1 x62 mus m Cam Pmatian 7 p 32m b b b b OneWay Functions 7 lnformally a oneway function is a function f such that x is easy to compute but its inverse is hard to compute A function is onetoone if x y whenever x y Given a onetoone function f the inverse off is the function g f 1 such that gy x iffx y The concept of inverse can be extended to nononetoone functions the inverse off is the function 9 such that gy 2 iffx y f2 for some 2 Limnsm Campmatianrp 31m L l Do We Have OneWay Functions Theorem Ifthere exists a oneway function f satisfying Def 1045 then P st NP Proof 9 For every lengthpreserving f we have an inverse of f which can be computed by a TM R in NP 0 R On input Mfzgt 1 Nondeterministically choose a string w lwl lzl 2 Call Mf on w lf Mfw I R accepts with output w otherwise reject 0 If P NP then there exists a deterministic TM E equivalent R E e P and PrEwEfw w 1 Condition 2 is violated and we cannot have any oneway functions Note If P NP we still do not know if there exist oneway functionsssmcmmammal De nition 1045 I A oneway permutation is a permutation f with the following two properties It is computable in polynomial time For every probabilistic polynomial time TM M every k and sufficiently large n if we picka random w of length n and run M on input w N4 PrMwlMfw wl S n l A oneway function is a lengthpreserving f with the following two properties It is computable in polynomial time For every probabilistic polynomial time TM M every k and sufficiently large n if we picka random w of length n and run M on input w N4 PrMwlMfw y wherefy fwl S 71 le As at Cam mm n 7 p 33m r Uses of OneWay Functions 0 Easy to encode but hard to decode j 9 Useful for secure password systems Difficult to use alone for general cryptosystems requires decode 0 Another kind of oneway functions are called trapdoor functions which can easily compute inverses decoding with special information ie keys L l mm m Cam Pmatlan 7 p 35m Candidates for OneWay Functions r 0 The multiplication function mult Let E 01 and for any 10 E 2 let multw 101 X 102 where w 101102 such that either lwll lwgl or lwll lwgl 1 Each binary string is treated as binary numbers Leading zeroes are padded to multw if lmultwl lt Eg w 1100101001 101 11001 and 702 01001 101 x wg 11100001 and multw 0011100001 le As at Cam mm 7 n 7 p 35m J 0 Digital Signatures PublicKey Cryptosystems make it easy Suppose Bob wants to send his signature to Alice Let M be the document to be signed Bob applies his own private key pgob to M O fpBob M b Cryptosystems PrivateKey Cryptosystems TWO parties who want to communicate over an insecure channel share a private key for encoding and decoding Problem Hard to change keys PublicKey Cryptosystems Each party has two keys one 2 Bob sends both M and O to Alice 3 Alice nds Bobs public key 9301 and decrypt C Is In the public domain and the other Is kept private using kBob X W430 O IfX M then Alice 1 Suppose Alice wants to send a message M to Bob knew it s Bob s signature 1 Alice finds Bob s public key kgob and compute C 1930177 M Sing kBob 2 Alice sends the encrypted message 0 to Bob 3 Bob uses his private key pBob to decrypt the message M 9p30b0 L Trapdoor Functions Indexing Functions in Atrapdoorfunction f z 2 x 2 a 2 is a lengthpreserving indexing 3 If we have a family of functions fi forz39 E 2 We j function that has an auxiliary probabilistic polynomial time TM G and an auxiliary function h 2 x 2 a 2 The trio f C an dh satisfy the following three conditions 1 f and h are computable in polynomial time For every probabilistic polynomial time TM E every k and sufficiently large n if we pick a random output M of G on 1 L and a random w of length n and run E on input 2 and w then N PrEwEi7 fiw ylwhere My fiwl S n 0 For every 71 every w of length n and every output 2 t of G that occurs with nonzero probability for some input to G ht ywhere Limits m Cam Pmatlan 7 in mm represent them by the single function f 2 X 2 gt 2 where f2 w mm for any 239 and w This f is called an indexing function f is said to be lengthpreserving if every f is lengthpreserving lensat Campmatian 7 39m Use of Trapdoor Functions TM G functions f and h are cryptosystem dependent RSA cryptosystem 1 G finds two large primes p and q a small integer e and computes N pq and the multiplicative inverse d Ofe modulo gtN 12 71W i 1 Le ed 1 mod gtN G1 returns t Ned 2 Ne is the public key and N d is the private key 3 fNyew we mod N 4 w M hltltNleldgt7 mu fwd mod N Rabin cryptosystem G1Gamal cryptosystem lensm Campmatmnrp Mm Theorems 78 and 711 illustrate important distinction Introduction among models of TM J b There is at most a polynomial difference between the time complexity of problems measured on deterministic singletape and multitape TM There is at most an exponential difference between the time complexity of problems measured on deterministic and nondeterministic TM Llrllltsat Computatioan m 22c131 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclal The University of Iowa Department of Computer Science The Class P lensatcampmmmnrp ma b b b Source of complexity Bruteforce search exponential time algorithms that solve problems by exhaustively searching through a space of solutions Example factoring a number into its constituent primes by searching through all potential divisors Note sometime bruteforce search may be avoided through a deeper understanding ofthe problem which may reveal polynomial time algorithms Llrllltsat Computatioan we Polynomial time Note Polynomial differences in running time are considered to be small whereas exponential differences are considered to be large Example Considerthe difference between growth rate of polynomial typically 713 and exponential typically 2 9 Form 1000713 1000000000 a large but manageable number 9 Form 1000 2 is a number largerthan the number of atoms in the universe ie an unmanageable number Conclusion polynomial time algorithms are fast enough for many purposes exponential time algorithms are rarely use ful lensatcampmmmnrp ans P is the class of languages that are decidable in polynomial Class P time on a deterministic singletape Turing machine ie P Uk TIMEnk Class P plays a central role in time complexity theory because 1 N P is invariant for all models of computation that are polynomially equivalent to the deterministic singletape TM ie P is mathematically robust P roughly corresponds to the class of problems that are realistically solvable by computers ie P is relevant from a practical standpoint lellsm Computatioan me Time complexity theory The aim of a time complexity theory is to present fundamental properties of computation ratherthan properties of Turing machines or any other particular 5 b model Therefore we focus on computations that are unaffected by polynomial differences in running time which are considered insignificant and thus are ignored This allows us to develop a theory that doesn t depend on the selection ofa particular model of computation Limnsatcampmmmnrp ans j b Notational conventions We describe algorithms using numbered stages where a stage is analogous to a highlevel step of a Turing machine or a sequence of simple steps of a Turing machine When we analyze an algorithm we need to do two things give a polynomial upper bound using 0 notation on the number of stages that the algorithm uses when it run on an input of length TL N examine the individual stages in the description of the algorithm to be sure that each can be implemented in polynomial time on a deterministic model When both tasks have been completed we can conclude that the algorithm runs in polynomial time because composition of polynomials is a polynomial lellsm Computatioan ans r 1 When a problem is in P we have a method to solve it in time 71 for b b Note 7 some constant k Whethernk is practical depends on k and on application Example running time 71100 is unlikely to be of any practical use But calling polynomial time the threshold of practical solvability has proven to be useful Once a polynomial time has been found for a problem that required exponential time some key insight have been gained and further reduction in its time complexity usually follows Limnsatcampmmmnrp ma Graph encodings Notations 0 Lists of nodes and edges Adjacent matrix M where Mz j 1 ifthere is an edge from node 239 to node j and Mz j 0 otherwise I We use the notation lt o gt to indicate a reasonable encoding of one or more objects into a string without specifying any particular encoding method b A reasonable method is one that allows for polynomial time encoding and decoding of objects into internal representations of computation model familiar encoding methods for graphs automata etc are reasonable 0 Running time of graph algorithms may be computed in number of nodes instead ofthe size of graph representation because graph representation is polynomial in number of nodes b Unreasonable encoding method are those that generate exponential large representations such as using unary strings 111 to encode natural numbers instead base k notation for k 2 2 should be used L l l leltsatcampmmmn rpm19 lensatcampmatmnrp ans Bruteforth algorithm for PATH The PATH problem r 1 A potential path is a sequence of nodes in G having a length at mostj yiPATH Gst l G is a direct graph that has a direct path from s to t j mwhere m Is the number of nodes In G Theorem 714 PATH E P 2 lfa direct path exist from s to t one having a length at most m exists because repeating a node is never necessary 3 The number of potential paths is 00 WhiCh is exponential in Note the bruteforce algorithm that examines all potential paths in G and number of nodes where k is the maximum number of successors Proofidea constrict a polynomial time algorithm that decides PATH determine whether any is a direct path from s to t is not fast enough Conclusion to get a polynomial algorithm that decides PATH we need to avoid the bruteforth approach L l l 1m avcam Putatan 411219 mm m Cam putatan 411119 b b Analyzing M Stages 1 and 3 are executed only once hence they are bound by 0m Stage 2 runs at most m times because each time except the last it marks an additional node of G Hence it is bound by 0m The total time is bounded by 20m 0m 0m letsmcampmmmn 7 W19 Proof A polynomial time algorithm M for PATH follows M quotOn input Gst where G is a direct graph with nodes 5 and t 1 Place a mark on node 5 2 Repeat until no additional nodes are marked a Scan all the edges of G If an edge 1112 is found going from a marked node a to an unmarked node 12 mark node 12 3 Ift is marked accept Otherwise rejectquot leiism Campmatmn 411319 b b b Proof idea Bruteforce algorithm to solve RELPRIME search through all j possible divisors of z and y and accept if none is greater than 1 The magnitude ofa number represented in any base k 2 2 is exponential in its representation base That is bruteforce search is an exponential running time algorithm letsmcampmmmn 411519 Another example 7 7 RELPPJME 1 y l x and y are relative prime For Ly E N x and y are relative prime if1 is the largest integer that evenly divide a and y Theorem 715 RELPRIME E P lensm Campmatmn 411519 L l Algorithm solving RELPRIME The following algorithm R solves RELPRIME using E R quotOn input Ly where my 6 N 1 Run E on Ly 2 le returns 1 accept Otherwise rejectquot Note clearly ifE runs in polynomial time so does R hence we only need to analyze E for time complexity and correctness leltsatcampmatlan 411819 A better idea Use Euclidean algorithm that determines the greatest common divisor oftwo number gcdxy to solve this problem Then if gcdxy 1 accept otherwise reject Euclidean algorithm E E quotOn input Ly where zy e N 1 Repeat until y 0 a Assign z I 1 mod y b Exchange 1 with y 2 Output lensm Campmatlan 411719 Analyzing E 7 Every execution of 1a except possible first cuts the value of I by a least halph because 1 mod y Teminderz div y and y 2 2 b 1 Since Teminderz div y lt y after stage 1b 1 lt y The values of z and y are reduced by at least half every time through the loop 1 b The maximum number of times loop 1 is executed is lessthan 2 092 z and 2 1092 y These logarithms are proportional to the length n of representations b Thus the number of times loop executes is bounded by 0n and E is polynomial lensm Campmatlan 411919 Introduction to Lex 22c131 222009 flex fast lexical analyzer generator Flex is a tool for generating scanners Flex source is a table of regular expressions and corresponding program fragments Generates leXyy cwhich defines a routine YYJEX 0 Format ofthe Input File The flex input file consists of three sections separated by a line with just in it definitions mm mm m0 i1 E D u ser code Definitions Section The definitions section contains declarations of simple name definitions to simplify the scanner specification Name definitions have the form name definition Example DIGIT 079 ID arz aizoi9 222009 Rules Section The rules section of the flex input contains a series of rules of the form pattern action Exam Ie inn prlntf quotAn 1dent1f1er snquot yytext u The yytextand yyength variable lf action is empty the matched token is discarded Action If the action contains a l the action spans till the balancing is found as in C n An action consisting only of a vertical bar 39 l 39 means quotsame as the action for the next rule The return statement as in C n In case no rule matches simply copy the input to the standard output A default rule User Code Section The user code section is simply copied to 18X yy C verbatim The presence of this section is optional if it is missing the second in the input file may be skipped In the definitions and rules sections any indented text ortextenclosed in and 9a s copied verbatim to the output with the is removed 222009 A Simple Example xi m humillnes u numichars u x u n l num711nes num7chars l l num7chars l u malnl yylexl prlntfl w of hues m a as chars muquot 5 num 111125 mum a Regular Expression Basics matches any single character except n malchzs 0 or more instances of mg przczd rig regular expression malchzs 1 or more nslanczs of m preceding regular expression 2 malchzs 0 or let M preceding regular expression malchzs m2 preceding or following regular expression d2fmzs acharaclzr class 0 groups enclosed regular expression we a W regular expression matches 2wng within m literally Example Regular Expressions gtlt match the character x xyz a characterctass x H l thts case the pattern tches etherah x a y ora z abroZ a character class thh a range l tL rhatches ah a a to a y letterfrom y through 0 or a AAVZ a negated characterctass x l e am character AAezm ahy characterEXCEPT ah uppercase letter or a hewhhe 222009 Lex Regular Expression W a de nition ofi x only tr followed byy y hot removed rrorh rhput xlm mto n occuhehces orx A x x but only at oegrhhrhg or the x but only at ehd orhhe s exactly what rs W the quotes except for and rottowrhg character A regular expression hhtshes wrth a space tap OrnerH ie Example Regular Expressions r zero or more rs where rts am regular expression H one ormore r s n ero orohe r s that s ah opttohat r rtzs anWhere from two to ve rs rm two orrhore rs rm exactlwl r s name the expansion orthe harhe de mllol i see above xyz foo the hterat sthhg xyz foo w r M ah a p r h r t or vK then the ANSer interpretation ofx otherwtse a hterat x used to escape operators such as W Example Regular Expressions 0 aNULcharacterASCHcode 0 123 the character With octatvatue123 XZa the character With hexadecimat vatue 25 r match an r parentheses are used to override precedence see betow rs the regutarexpressioh rfoHoWed by the reguiar expression s caiied concatenation ris eitherah roran s Ar an rbui ohiy at the beginning ofatihe i e wnicniusi starting to scan or right aftera newiine nas been scanned rs an r but ohiy atthe end of a iine i e Just before a newiine Equivateht to rh 222009 Metacharacters e metarcharacters do not match inernseives because they are used in the preceding reg exps 0 tLJU irmt W 7 to match a metarcharacteiquot prefix With r to match a backstash tab orneWtihe use t 0rri Regular Expression Examples en integer 12345 1909 a word cei uzAZ e pass bly signed integer 12345 or 12345 gt1909 e floating point number 12345 o9quotquot09 Two Rules 1 lex will zlvmys match the lungest number ul39 characters taken p nssib le 2 Il39twu ur mare pussible mkens are nl39 the same length then the EXP taken with the regular ressinn that is defined rst in the lex speciricatiun is ravured 222009 Regular Expression Examples c comment call foo herell w white space t English sentence Look at this tla zAZ mm x Special Functions yylext 7 where text matched most recentli is stored yyleng 7 number of characters in text most recently matched val associated value of current token 9 yymore 7 append next string matched to current contents of yylexl yyless n 7 remove from yylext all but the rst n characters io unputc 7 return character c to input stream ra 7 may be replaced by user method is called by the lexical analyser whenever it inputs an EOF as the rst character when trying to match a regular expression A Simple Example M 1m humillnes n numiwurds n x word Leemezh 1 n u 201 lt numillnes ward lt num7wurds gt malnl yylexl prlntfl w of huee m a as words muquot num as gt hues numiwur 222009 A Simple Example 1n numillnes u numichars u x x n num711nes numichars lt numichar5 gt malnl yylex t prlntfl w of huee m a as chars muquot nu millnesy numichars Resources Google directory of lexer and parser generators Flex homepage httgjflexsourceforgenet A Turing machine is similar to a finite automaton with 0 b Turing Machines supply of unlimited memory A Turing machine can do everything that any computing device can do There exist problems that even a Turing machine cannot solve lellsm Computatioan 2m 22c131 Limits of Computation Hantao Zhang httpwwwcsumwaeduthhangclsl The University of Iowa Department of Computer Science Limnsatcampmatianrp 1m N 00 F TM versus FA an FA can only read its input once write A TM can both write on the tape and read from it move The readwrite head of a TM can move both to the left and to the right and some moves are not defined an FA can move in one direction only and its next move is always defined DFA only size The tape ofa TM is infinite the input ofan FA is finite accept FA accepts a string when it has scanned all the input symbols and enters a final state TM accepts a string as long as it enters a final state one suffices lellsm Computatioan mo 0 Memory is modeled by a tape of symbols Tape 0139 a Turing Machine TM 1 Initially the tape contains only the input string and is blank everywhere else 1 If a TM needs to store info it may write on the tape To read the info that it has written TM can move its head back over its tape 0 TM continues to move until it enters a state whose next move is not defined Limnsatcampmatianrp 3m Example TM computation Construct a TM M1 that tests the membership in the language L1 ww la 6 01 0 so if first symbol is 0 or 1 replace it by x remember it as a if it is u goto 55 else reject 0 511 move right until if no 7 before u reject 0 521 move right until 0 or 1 if the current symbol is the same as a then replace it by 9 else reject 0 53 move left until 0 54 move left until ac and goto 50 L1 55 move right until 0 1 or u accept ifu reject if 0 1 lelsm Campmatmnrp 5m Example TM computation Construct a TM M1 that tests the membership in the language L1 ww la 6 01 In other words we want to design M1 such that M1w accept iffw 6 L1 lensatcampmmmnrp 5m Computations WM Q7 27 F7 67 107 gaccph Ireject compl Ites as fellows j 0 M receives as input w 11112 an e 2 a e 2 written on the leftmost squares of the tape and the rest of the tape is blank ie filled with u 0 The head starts on the leftmost square of the tape 0 The first blank encountered shows the end ofthe input 0 Once it starts it proceeds by the rules defined by 6 0 lfM evertries to move to the left of the leftmost square the head stays in the leftmost square even though 6 indicate L 0 The computation continues until M cannot move if M enters qaccept the input string is accepted M may go on forever as long as 6 is defined lelsm Campmatmnrp am Formal de nition A Turing machine is a 7tuple j M Q7 27 F7 67 107 gaccph Ireject Where Q7 27 F are sets and 1 Q is a set of states 2 E is the input alphabet and u g E 0 F is the tape alphabet u e 1 E C F 6 Q x F a Q x F x LR is the transition function go 6 Q is the initial state qaccept e Q is the accept state sometimes denoted qa ame Inject E Q isthe reject state sometimes denoted qr Note qreject is optional in the definition lensatcampmmmnrp 7m I b 5 Example TM computation 53 move left until 653a 53aLwhere a E 0 1x653 54 L 54 move left until ac and goto 50 654a 54aLwhere a E 01654x 501R 55 move right until 0 1 or u accept ifu reject if 0 1 655x 551 R655U 5a ULgt leltsatcampmatlan 41me Example TM computation a if it is u goto 55 else reject 65005101R65015111R650 551R b 511 move right until if no before u reject 681a70 81a707Rgt7651a71 511 1 R651a 521 R 521 move right until 0 or 1 if the current symbol is the same as a then replace it by 9 else reject 682a71 82007067 Rgt765207 0 lt83CELgt68211 531L b 1 so if first symbol is 0 or 1 replace it by 2 remember it as lensatcampmatmnrp 9m b b Formalizing TM computation A configuration 01 yields a configuration 02 ifthe TM can legally go from 01 to 02 in a single computation step Formally suppose abc E F 111 6 F and 141 6 Q 1 We say that ua 1 b1 yields uac qj 1 if 601119 QjC R machine moves rightward 2 We say that ua 1 b1 yields u qj 101 if 6qb qjcL machine moves leftward leltsatcampmatlan 4112f Con guration A con guration 0 ofM is a tuple O u 12 where q E Q M E F is the tape content and the head is pointing to the first symbol of 2 Configurations are used to formalize machine computation and therefore are represented by special symbols b Tape contains only M following the last symbol ofv lensm campmmn 411M Example 2 M2 is a Turing machine that decides A 02 l n 2 0 some elementary M2 On input string w number ofO is odd reject N If in stage 1 the tape contained a signle 0 accept 90 Return the head to the lefthand end of the tape 5 Go to stage 1 Sweep left to right acrossthe tape crossing off every other 0 if the Limitsmca lpmmmn 411M Head at one input end Given M Q7 27 F7 67 107 gaccph Ireject For the lefthand end b n the configuration qi by yields qj cu if the transition is left moving le 6012312 qjcL the configuration qi by yields 6 qj v forthe right moving transition le 6012312 qjcR For the righthand end b 9 the configuration ua qi is equivalent to ua qill because we assume that blanks follow the part of the tape represented in configuration Hence we can handle this case as the previous lensat Campmatianrp lam Example 2 j Return the head to the lefthand end of the tape 6q3lJ ltq5LlLgt 601511 ltq5aLgt for a 6 01 N Go to stage 1 b 51157U 1127MB 7 Limitsmca lpmmmn 4115f Example 2 j number of 0 is odd reject a Markthe first 0 by U 1170 lt427U7Rgt b Cross off the next 0 after M 601270 ltq3vzvRgt 0 Pass 0 at odd position cross off 0 at even position Sweep left to right acrossthe tape crossing off every other 0 if the 7 6q30 ltq40Rgt6 J40 ltq3zRgt 6qI ltqzRgt for q 6 11271137114 d lfthe number ofO is odd reject 6q4u ltqlJRgt If in stage 1 the tape contained a signle 0 accept 6012M qa7U7Rgt M lensat Campmatianrp 15K Accepting an input 11 A Turing machine M accepts the input 10 ifa sequence of configurations 01 02 On exists such that 1 01 is the start configuration 01 541010 2 Each 01 yields Ci1i12n 71 3 On is an accepting configuration letsmcampmmmn 411M Special con gurations the start con guration 0 ua qacceptbv is called accepting con guration b ua qrejectbv is called rejecting con guration 5 halting con gurations fthe input of M is w and initial state is 10 then 10 w is Accepting and rejecting configurations are also called leitsat Campmatmn 411V Turingrecognizable language A language L is Turingrecognizable ifthere is a Turing machine M that recognizes it 7 mus m Cam Pmatmn 7 in 2mm Language of M r LM w E 2 l M accepts w 7 lensat Campmatmnrp 19m Fail to accept Note When we start a TM on an input 10 three cases can happen 0 TM fails to accept w by entering 1mm and thus rejecting or by looping 1 TM may accept w 0 Sometimes it is difficult to distinguish a machine that fail 2 TM may reject w to accept from one that merely takes longtime to halt 3 TM may loop Indefinitely Ie TM does not halt Note looping does not mean that machine repeats the same steps over and over again looping may entail any simple or complex behaviorthat never leads to a halting state Question is this real le can you indicate a computation that takes infinite many steps without repetition lellsmcampmatlan 7 22m lensm Computatioan 21m Turingdecidability Decider is A decider that recognizes some language is also said toj rA TM that halts on all inputs is called a decider j decide that language 9 A language is called Turingdecidable or simple decidable if some TM decides it lellsmcampmatlan 7 2m lensm Computatioan 23m n We can give a formal description of a particular TM by J b Higher Level Descriptions specifying each of its seven components Defining 6 can become cumbersome To avoid this we use higher level descriptions which are precise enough for the purpose of understanding We want be sure that every higher level description is actually just a short hand for its formal counterpart mus m Cam Pmatian 7 p 25m b b b b Note Any regular language is Turingdecidable Any contextfree language is Turingdecidable Every decidable language is Turingrecognizable a language is Turingrecognizable if it is recognized by a TM Certain Turingrecognizable languages are not decidable to be decidable means to be decided by a TM which halts on all inputs lellsm Computation 7p 25m 5 Analyzing M3 In stage 1 M3 operates as a finite automaton no writing is necessary as the head moves from left to right 5qoluqalulRquO IMJLR 601271 qivvav 601276 q3vcvR 601376 qscR 544717 11471171301 5447U anUVR 9150 61107 1 qlvAvR16qlvb Imble 6417U gay yR mus m Cam Pmatian 7 p 2w M3 is a Turing machine that performs some elementary Example 3 arithmetic lt decides the language Oaib739ck lz39xjkz397jk2 0 M3 On input string w 7 1 Scan the input from left to right to be sure that it is a member of 0 5 a b c reject if it is not accept if it is e at or 12 Set the head pointing at the first a on the tape Cross off an a and scan to the right until a 12 occurs Shuttle between the b s and as crossing off one of each until all b s are gone Restores the crossed off b s and repeat stage 2 ifthere is another a to cross off If all as are crossed off check on whether all as are crossed off If yes accept otherwise rejectquot le ns m Cam Pmatian 7 p 27m 3 crossa 2 ndingthe rsta 5015714 167 U7 R 5 5137 U 157 ML 1 6q67a 17714 R 61571 1517L for x E 171970 6167b 187 57 L 6 187 U 177E7 R 5017 177a7Ry 501773 177373 501775 197 7B 501975 1975713 501970 1970713 501970 011070711 Limilsmcampmmmn 7 3mm lensm Campmatian 7 29m Example 4 Element distinctness problem r M4 Q E F 6 157 qa qr is the TM that solves the element j Given a list of strings over 07 1 separated by 7 determine distinctness problem if all strings are different A TM that solves this problem accepts the language E r1z2mzk l xi 6 01zi zj for i7 j M4 works by comparing 1 with 12 xk then by comparing mg with 13 xk and so on Limilsmcampmmmn 7 32m lensm Campmatianrp 31 m b b b b Marking tape symbols In stage two the machine places a mark above a symbol 7 in this case In the actual implementation the machine hastwo different symbols 7 and 7 in the tape alphabet 2 Thus when machine places a mark above symbol a it actually write the marked symbol ofx at that location Removing the mark means write the symbol at the location where the marked symbol was Assumption all symbols ofthe tape alphabet have marked versions too mes m Cam Pmatlan 7 p am Informal description M4quotOn input 102 1 N 0 J U1 Go to stage 3quot Place a mark on top of the leftmost tape symbol If that symbol was a blank accept If that symbol was a continue with the next stage Otherwise reject Scan right to the next and place a second mark on top of it If no is encountered before a blank symbol only I was present so accept By zigzagging compare the two strings to the right and to the left of the marked lfthey are equal reject Move the rightmost ofthe two marks to the next symbol to the right If no symbol is encountered before a blank symbol move the leftmost mark to the next to its right and the rightmost mark to the afterthat This time if no is available forthe rightmost mark all strings have been compared so accept lensatcampmatmnrp 33m Computation History The computation history for a TM on an input is the sequence of configurations that the machine goes through 22c Limits of Computation as it processesthe input 39 Hantathang Note the computation history of TM M is a complete record mpWW VumwaveduthhangCm ofthe computation performed by M The University of Iowa Department of Computer Science Computation Histories leltsat Campmatmnrp 255 lensatcampmatmnrp 155 Note Computation histories in Computation histories are finite sequences j rLet M be a TM and w an input string An computation j If M does not halt on w no accepting or rejecting history for M onhw is a sequence of configurations computation history exists for M on w 017 027 39 39 39 7 Ok W ere39 Deterministic machines have at most one computation 139 01 395 the Start Conf39gurat39on Of M on w history on a given input 2 0H1 legally follows from Oi according to the transition Nondeterministic machines may have many funCt39on 0f M computation histories on a single input corresponding We distinguish two kind of histories to Various ComPUtation branChes39 0 Accepting computation history Ck is an accepting configuration of M 0 Rejection computation history Ck is an rejecting configuration of M leltsat Campmatmnrp M55 lensatcampmatmnrp 355 Schematically Figurel Linear Bounded Automata A LBA is a restricted type of TM wherein the tape head isn t permitted to move offthe portion of the tape containing the 55555 input Figure 1 Schematic of a LBA If the machine tries to move its head off either end of the input the head stays where it is in the same way that the head will not move offthe lefthand end ofthe ordinary TM s tape lelism Computatioan 555 lensatcampmmmnrp 555 Observations Note 77 7 0 Despite their memory constraint LBA are quite n A LBA is a TM with a limited memory as shown in powerful Figure 1 9 Deciders for ADFA EDFA Acpg Ecpg all are LBAs A LBA can only solve problems requiring memory that 9 Most practical computing problems can be solved by an can t W39th39n the tape used as 39an39t39 LBA Using a tape alphabet largerthan input alphabet allows the available memory to be increased up to a constant factor For an input of length n the memory amount available is linear in n hence the name of the model b lelism Computatioan 855 lensatcampmmmnrp 755 Lemma 58 A solvable problem Let M be an LBA with 1 states and 9 symbols in its tape i i Problem testing whether an LBA accepts an input is a alphabet There are exactly qng distinct configurations of solvable problem M for a tape of length n Language the language ALBA Proof ALBA i M is an LBA that accepts string w 9 A configuration Of M is a tuple state headpositian tapeCantents I M has q states is decidable 0 Length of input is n so the head can be in 71 positions 0 Only 9 possible strings can appear on the tape Hence qng is the number of different configurations of M L lellsmcampmmmn 7 mm lensatcampmmmnrp 955 Loop Detection Theorem 59 if As it computes M goes from configuration to j iiALBA is decidable j conf39gurat39on Proof idea to decide whether LBA M accepts w 0 If M ever repeats a configuration it would go on to Simulate M on w repeat this configuration over and over again and thus looping 0 During the simulation if M halts and accepts or reject acce ts or re39ects accordin l 0 Since M is an LBA it has only qngquot different p J g y con gurations Hence if it performs a number of Steps 1 If slmulatlon does not halt detect the loop so that one larger than qng and it did not halted then M repeats a can ha and reJect configuration and thus it loops lellsmcampmmmn 411258 lellsat Campmatlan 7 1155 Observations Theorem 59 shows that LBA and TM differ in one essential way for LBAs acceptance problem is decidable while for TMs it is not Certain other problems involving LBAs remain undecidable Example emptiness problem b ELBA M l M E LBA LM 2 is undecidable Limitsatcampmatmn 421355 Proof The algorithm that decides ALBA is L quotOn input ltMwgt M and LBA w a string 1 Simulate M on w for qng steps or until it halts 2 IfM halted accept if M has accepted and reject if M rejected IfM has not halted reject lensm Campmatmnrp 1355 Using E L B A decidability b constructing an LBA B and testing if LB is empty b LB 7 I if M does not accept LB 2 Hence if we can detect whether LB is empty we termine whether M accept to L For a TM M and input w determine whether M accept w by Language recognized by B consists of all accepting computation histories of M on w If M accepts LB contains one string and so 7 can de Limitsatcampmatmn 7 1555 Theorem 510 7 ELBA is undecidable Proof idea By reduction from ATM show that if ELBA is decidable then so is ATM lensm Campmatmn 411558 LBA B works as follows Constructing B form M and w n Breaks up as determining configurations 01 027 Ck We need to show how a TM can obtain a description of B from M and w 9 Construct B to accept its input as if x is an accepting computation history for M on w 1 Check the conditions 1 Cl isthe start configuration forM on w ie Cl qowlwz t go the start state of M N Each CH1 legally follows from 02 ie verifythat Cz and CH1 are Note the accepting configurations of B are represented as single strings Identical except for the positions under and adjacent to the head with con urations 8e arath b i e in 02 These positions must be updated according to the g p y 39 quot transition function ofM z 01Cz t t t 0 Ck is an accepting configuration for M on w ie Ck contains qaccept 0f M 90 leltsatcampmmmn 421555 lensai Campmatlari 411758 Proof Note j 7 0 Item 2 above can be verified directly from the transition function 6 j Suppose that TN R decides ELBA Construct TM S that This is shown in Figure 2 for 601311 q5zR decides ATM as follows I Item 2 above can be performed by zigzagging between S quotOn input ltMwgt M a TM and w a string corresponding positions of 02 CH1 1 Construct LBA B from M and w as described above 2 Run Ron input B 3 If R rejects accept if R accepts rejectquot i i1 Figure 2 Checking computation history L A L 7 leltsatcampmmmn 7 zusa lensai Campmatlarirp 1958 Theorem 513 Problem Test whether a CFG generates all possible strings over its terminal alphabet 2 Language the language ALLCFG GiG CFG LG 2 Theorem ALLCFG is undecidable Proof idea by contradiction Assume that ALLCFG is decid able and show that then ATM is then decidable L mus m Cam Pmalian 7 p 2255 Note If R accepts B then LB Q thus M has no accepting computation on w and M does not accept 10 Consequently S rejects Mm I If R rejects B LB Q Since the only string B can accept is an accepting computation history for M on w it means that M accepts 10 Consequently S accepts M710 This is a contradiction so R cannot exist Limnsat Campmatianrp 21 55 Strategy 7 I An accepting computation history for M on w hasthe form 0102MCk 0 Hence G generates all strings that 1 do not start with Cl 2 do not end with an accepting configuration 7 3 for some 2 C does not properly yield CH1 underthe rules ofM mus m Cam Pmalian 7 p ma Proof idea continuation 7 Using the decidability of ALLOW one can devise the following decision procedure for ATM b For a TM M and input w construct CFG G that generates all strings over the extended alphabet of M iff M does not accept w b If M does accept w C does not generate a particular string which is the accepting computation history for M on w Note G is designed such that it generates all strings that are not accepting computation histories for M on w musm Campmatian 7 2355 Proof idea continuation Theorem 514 Using the decidability of 2EOF0 one can devise the l Problem Test whether the intersection of two CFLs is empty following decision procedure for ATM Language The language I QECFG ltG17G2gtlG17G2 CFCALltG1gtQLltG2gt Ql J For a TM M and Input w construct CFGs 01 and 02 such that LGl LGz contains a particular string which is the accepting The rem 2ECFG 395 undeCldable computation history for M on w ifM accepts w Proofidea By contradiction Assume that 2ECFG is deCIdable 0 IfM does not accept w LGl LGz does not contain anything and show that then ATM is then decidable Limitsatcampmatian 7 2555 Limitsat Computation in 2555 Constructing G2 Constructing G1 G2 We generate a pair of configurations 01701111 if CH1 j liGl At first we start with the start configuration and then j legally follows from 01 according to the transition function of generate a pair 0f configurations C 0i1 if CH1 legally M follows from 01 according to the transition function of M SPl 1 SqowP PHAPle PHAPlC AHaAaforanya e F A gt anbp if 6qa pbR BHaBa l foranyael I I J AHaAaforanya e F I A 4 anpb if 6qa pbR I BHaBala oranyaeF bbbbb C a an accepting configuration Limitsatcampmatian 7 ma Limitsat Computation in 2755 Application Use the theorem 513 to show that EQCFG ltGHgtl G and H are CFO and LG LH is undecidable Solution Assume EQCFG were decidable Construct a decider M for ALLCFG GlG OFGLG 2 by M quotOn input G 1 Construct CFG H such that LH 2 2 Run the deciderfor EQCFG on ltGHgt 3 If it accepts accept if it rejects rejectquot L mes m Cam Mummy 7 p ausa Property of G1 and G2 I 01 generates a sequence of configurations 01C 3m02k710 02 generates a sequence of configurations 01C 3 l Cikilc b b such that 02241 follows 022 legally such that 022 follows Caz1 legally LGl LGz contains only an accepting computation history lensm Campmatlan 7 2955 A Puzzle Kind Description Puzzle is a collection of dominos like l l ll ll aTbcH 7 A match is a list of these dominos repetitions permitted so that the string we get by reading offthe symbols on the top is the same as the string of symbols on the bottom Example l ll l ll llaTul Reading off the top string we get abcaaabc Reading off the bottom string we get abcaaabc which is the same L mes m Cam Mummy 7 p 3255 Note r M decides ALLCFG assuming that a decider for EQCFG ex ists Since we know that ALLCFG is undecidable a contra diction result lensat Campmatlan 7 31 55 Observation Note For some puzzle finding a match may not be possible We can also depict a match by deforming the dominos For example the puzzle W m WU so that the corresponding symbols from top and bottom 1 E 7 7 7 bu lineu Fi ure3 cannot contaInamatch 390 g a b C a a a b C a b C a a a b C Figure 3 Deforming dominos Reason 1 top string is longerthan the corresponding bottom string leltsatcampmatmn 7 ma lensat Campmatmnrp 3355 Mathematical formulation Post correspondence problem An instance of PCP is a collection of dominos j Determine whether a collection of dominos has a match j Plfl7l lwwl l A match is a sequence 2112 z l of P components where N te quot5 PrOb39em 395 unSOIVable by algorlthms tiltiz til bilbiz bil PCP determine whether P has a match Notation PCP l P instance OfPCP with a match leltsatcampmatmn 7 3555 leltsat Campmatlarv 7 3555 Theorem 511 Other formulations POP is undecidable An instance of PCP over 2 consists oftwo Proofidea by reduction from ATM via accepting computation histories J COHSldertWO llStSi A 11 l l l 7171 and B yll l l 7an 123 E 2 I Show that from a TM M and input w we can construct an instance P 1 S 2 S n of PCP where a match is an accepting computation history for M on 1 DO there BXlStS a sequence 13917 l l vim 0f integers SUCh that w zijtttzimyi1tuyim b If we could determine whether this instance of PCP has a match we Note To show the correspondence the lists A and B can be written would be able to determine whether M accepts w 9 Since ATM is undecidable we cannot determine whether P has a g w VE Iiryi E 2quot match Technical details Constructlng P is For convenience in the construction of P we assume j 7 0 Choose dominos in P so that making a match forces a j that M on u never attempts to move its head off the simulation of M to occur lefthand end ofthe tape we need to alter M to prevent such behavior 0 In the match each domino links a position or positions in one configuration with the corresponding ones in Alter PCP to require that a match starts with the first the next configuration domino 5 This is called modified PCP MPOP MPCP ltP l P instance of PCP with a match that starts with first domino 5 Note we will show later how to remove this requirement L l l leltsmcampmatlan 7 ma leltsat Campmatlan 7 3955 Mapping P into P 0 Let u ulug un a string of length n Define the following three strings uu1u2ugmun uu1u2u3mun uu1u2ugmun If P were gm 2 k li lyl tilill7llymyllyl L A mus m Cam Pmatiari 7 p ma 0 Proof Let TM R decide the PCP and construct S deciding ATM LetM QyziFy yqoiqayqr and w E 2 l The TM S that decides ATM constructs an instance of the PCP that b b has a match iff M accepts w S constructs first an instance P of MPCP This construction has seven parts to be carried out shortly To convert P to P an instance of PCP build the requirement of starting with first domino directly in the problem so no need to state it explicitly Limnsaf Computatioan Msa Construction of S Part 1 T 7 Put qO wjfm into 13 as its first domino if Note because P is an instance of MPCP the match must begin with this domino The bottom string begins correctly with Cl qowlwz t t l mm the first configuration ofthe accepting computation history for M on w as seen in Figure 4 Figure 4 Beginning ofthe MPCP match L A mus m Cam Pmatiari 7 p Msa j b b Note Considering P an instance ofthe PCP we see that only domino that could possibly start a match is the first one it This is because it is the only domino where both the top and the bottom start with the same symbol namely Beside forcing the match to start with first domino the presence of s doesn t affect possible matches because they simply interlieve with the original symbols which occur in the even positions ofthe match The domino Log is there to allow the top to add the extra at the end of the match Limnsaf Computation in ma Construction of S Part 2 Let M Q727F767q07qa7qr and w E 2 For every ab E F and every 177 E Q q qr if 6qa 731 R put g into 13 mes m Cam Pmatmn 7 p ma Note 0 In part 234 ofthe construction we add to P dominos that perform the main part ofthe simulation 0 Part 2 handle head motions to the right part 3 handles head motions to the left and part 4 handlesthe tape cells not adjacent to the head lelsm Campmatmn 7p ma Construction of S Part 4 r Let M Q2 16 q07qa7 qr and w E 2 For every 1 E F put 3 into 13 7 Illustration to construct a hypothetical example showing what we did so far we choose 2 012 F 012U w 0100 6q00 q72R mes m Cam Pmatmn 7 p ma r and every w e Q q qr mg a 7 r b L put l Construction of S Part 3 Let M Q 2 16 107 qr and w E 2 For every a 190 6 F 5 Tab 7 into 13 m ns m Cam Pmatmn 7 p ma The match constructed so far Illustration continuation T 0 Part 1 places 3 11 in P qu 1 o 0 qu100 1 Part 2 places 073 in P as 6q0 0 17 2 R 400100 2 17 1 0 0 if 0 Part4 places the dominos 5 in PC Limitsmcampmmmn 7 sum lensm Computatioan ma Continue the example Construction of S Part 5 liAssume that in state 17 upon reading 1 M goes into state j rPut g and fig into 13 j 15 writes 0 and moves head to the right ie 601771 1570713 Le 6 P Hence latest partial match 0 The first of these dominos allows us to copy the symbol 7 that marks the separation of configurations 2 171 0 0 l The second domino allows us to add blank symbol u at the end of a configuration to simulate infinitely many blanks to the right that are suppressed when we write 710 2 0 15 0 0 the configuration extends to Limitsmcampmmmn 7 5255 lelsm Computater 7 5155 Observations Note a As we construct the match we are forced to simulate M lf 6q5 0 qg 27 L then we have dominos 0 w 3332 32 222 33 This Process continues untii M reaCneS a halting Staie Note the first domino is relevant because symbol to the left If an accept state occurs we want to let the top of ofthe head is 0 and the preceding partial match extends to partial match catch up with the bottom This is done by 2 01150 a Part 6 20q500 2 qgoz 0 Limitsmcampmmmn 7 ma lensm Campmatmnrp 5358 Construction of S Part 7 Construction of S Part 6 iiFinally add the domino hf and complete the match j iiFor every 1 E F put if into P j Part 6 has the effect of adding pseudostepsquot to the TM M after it halted where the head eats adjacent symbols until qa qa non are left Limitsmcampmmmn 7 5555 lensm Campmatmnrp 5555 PCP over 2 07 1 is undecidable Proof idea by reduction from PCP Reduction 1 Construct a computable function Encode that takes a PCP instance of any finite alphabet and produces a binary alphabet PCP called BPCP I Since PCP is undecidable so is BPCP leis m Cam Pmatlan 7 p 5555 A decidable version of PCP Problem PCP over the alphabet E 1 is decidable Proof we describe a TM M that decide the unary PCP l Considerthe unary instance of PCP P i Z t t t g The machine M performs as follows M quotOn input a1b1mambngt 1 Check if 1239 122 for some 2 if so accept 2 Check if there exist z j such that 1239 gt 122 and aj lt b If so accept otherwise rejectquot lensm Computation 7 5755 Introduction to yaoc 22c1131 2112009 Yacc Overview Parser generator r Takes a specification for a contextfree grammar r Produces code for a parser Output Ccude W a 53 E van impiementing a parser grammar mies Mm nd aetruns Dr bisun ton yyumu E defauil yll ScannerParser interaction o Parser assumes the existence of a function int yylex that implements the scanner 0 Scanner r return vaiue i dicates tne type oftoken fou v othervaiu s communicatedto tne parserusm yyt xt yylval o Yacc determlnes Integer representatlons for tokens Communicatedto scannerm we y a 7 use yacc d to p ytabh r Token encodi rid of We represente b 0 a characterhterai its ASCH vaiue othertokens assigned numbers 2 257 2112009 Using Yacc lemel rules Evamrmv rules mmmrermm int yyparse Called once from main zsestuppied Repeatedly calls yylex until clone e On syntax error calls yyerror usersupplted e Returns 0 if all ofthe input was processed e Returns 1 if aborting due to syntax error Exa male rnt memo t return Wparsem yacc input format A yacc input le has the following structure defmlOHS n n reeurree Shunest pusslble legal yacc rnput 2112009 Definitions 0 Information about tokens S r declared using token39 singlecharactertokens don39t have to be declared any name not declared as a token is assumed to be a nontermlnal 7 start symbol of grammar using start optional operator info precedence associativity stuffto be copied verbatim into the output eg declarations includes enclosed in Rules Grammar production yacc rule As 1 2 M A 5152 am A9010 oquot q lclcz cquot A9010 of l 02 of v WW mm m Rule RHS can have arbitrary C code embedded Within E 39 g A B1 printf atter B1nquot x 0 B2 x B3 Leftrecursion more efficient than rightrecursion AAx ratherthan AxA Conflicts Conflicts arise when there is more than one way to proceed with parsing Removing conflicts r specify operator precedence associativity restructure the grammar 7 use youtput to identify reasons for the con ict 2112009 Specifying Operator Properties o Binary oerators quotnleft quotnright nonassoc2 wen w w Operators in the same gruup r ave the sarne precedence nght W o Unary operators pre r Changes the precedence ofa ruie to be that of the token specrneo E g wen wen m Exp exnrw expr i 7 exp r lame i Specifying Operator Properties o Binary operators left right nonassoc wen w wen rr nght W Across mu s recedence rncreases gcnng duvvn o Unary operators pre r Changes the precedence ofa ruie to be that of the token E 9 m Exp Expv expr i e expr pvec i Specifying Operator Properties o Binary operators left right nonassoc wen w wen DurightV o Unary operators prec Changes the precedence ofa ruie to be that ofthe token 9 specrned E wen quot 9 The ruie fur unary 4 has the Em 2 2 quot sarne hrgh precedence as iuexpr quotnamesquot i mmmrarsme 2112009 Error Handling o u The token error is reserved for error handling a can be used in rules 9 suggests places where errors might be detected and recovery can occur I IF error 5m interrdsutnizr mmmrmm w Placing error tokens Some guidelines Close to the start symbol of the grammar To allow recovery without discarding all input Near terminal symbols r To allow only a small amount of input to be discarded on an error gt Considertokens ke that follow nonterminals Without introducing conflicts Error Messages On finding an error the parser calls a function void yyerrorchar s l 5 points to an error msg r usersupplied prints out error message More informative error messages gt int yychar The token number causing the error gt user program keeps track of line numbers as well as any additional info desired 2112009 Error Messages example inciude ytab h extem imwchar curriline static V id printituko vmu Werrurchar s mnnmsmem h 255 iine quotnu quotns x W ar lt print stdern nnc x Wchar Bummer 5 E S printituko switch WcharH case iD case iNTCON l Debugging the Parser To trace the actions of the parser when compiling 7 de ne YYDEBUG b at runtime r set yydebug 1 P extern int yydebug Adding Semantic Actions Semantic actions for a rule are placed in its body an action consists of C code enclosed in may be placed anywhere in rule RHS Example expr ID symeIIookupidname decl typename tval idist 2112009 Synthesized Attributes Each nonterminal can return a value 9 The return value for a nonterminal X is returned to a rule that has X in its body eg A x r value wetumee W x This is different from the values returned by the scanner to the parser Attribute return values To access t a rule bod r an action occurring in a rule body counts as a symbol 39 decl type tVal 1 ldillst Symtblilnstall Walt T i e i he value returned by the Ih symbol in us i To set the value to be returned by a rule assign to 39 gt by default the value ofa rule is the value of its rst symbol Le 35 mmmtmme An example statement Expresslun printh ngn 1 expresslun expresslun w expresslun t st sat t expresslun expresstentss st 43 lNUMElER 1 nn n statement Accurdlng these Wu pruductluns Expresslun 5473leparsedlntu Expresslun exmessten number expiesslun Expresslun number exmessten exmessten nurlnber nurlnher 5 o t e 3392 2112009 Choosing a Grammar SgtE E ET EgtET Precedence and Associativity right 39 eft eft 39r right 391 Defining Values expr expr 3939 term term term term 3939 factor factor factor 3939 expr 3939 ID NUM 137 1 1 53 51 2 2112009 Defining Values 1 expr expr 3939 term 55 51 53 i term i 51 term term 3939 factor 55 1 53 i factor is 1 factor 3939 expr 3939 55 52 I ID mm Defining Values expr expr 3939 term 55 1 3 r te m 55 1 term term NU factor 5 1 3 factor 5 1 factor 3939 expr 3939 5 52 Defining Values expr expr 3939 term 5 1 3 term 5 1 term term 3939 factor 5 1 3 factor 5 1 factor 3939 expr 3939 5 52 ID mm L 3 Default 1 so I one Example Lex xi canoe on include ltstdiohgt include 17 tahh vs id 732RZ7azn7207939 quotSEE tn semi u cumma L XX int return I har return cnnn oat ret n non cumma return Co semi return SEMI return wspc 2112009 Yacc Example Definitions 8 l include ltstdio hgt include ltstd1ib hgt l tstart line ttokeh CHAR comma FLOAT In INT SEMI at Yacc Example Rules This production is not part of the quotofficialquot grammar It39s rimary purpose is to recover from parser errors so its probably best if you leave ot here 1ine nothing V I line dec I line error i pintfquotFailuze nquot k yyerro yyclearin 2112009 Example Rules m1 type 1 1m plintf Success39n m 1m cum 1 1m type 111139 I cm l mm m extern nu yyin mainO an arseo while I fenfyyin yyerrnr char as Dnn t have m dn anythingl Another Example vavjec MEMUMJUbSEHM MsMbUmkumM NULL EnMSEC mumme ueuavauuns x w as r msen mam mm meuuame w WmlbLm aHm RRAV upLsubsch r wcoN H m ARRAVJ FnuH l m u wanasuype ARRw iamwaexemnmpe quotwan WabaseJHE quotwan SLEnwaexemenLvpe UNDEF gt 2112009 Conflicts A conflict occurs when the parser has multiple possible actions in some state for a given next token Two kinds of conflicts shiftreduce con ict 7 The parser can either keep reading more ofthe input shill actionquot or it can mimic a derivation step using the input it has read already reduce actionquot reducereduce con ict There is more than one roduction that can be used for mimicking a derivation step at that point mmeieume Example of a conflict Grammar rules Ssirteis r i w input ifeiifezSzelseSJ i ifeSelseS quot139 Parser state when input taken eise input already seen if e1 cneiees rer cuntiriuirig i keep reading input snirt 2 rnirni Erivatiuri step using euuee else part at innerrnest if I rt est it eventual parse strueture eventual parse structure Ife lfezSzelseS fe lfezSzielse53 shiftrreduce con ict Handling Conflicts General approach a Iterate as necessary t Use vacc 7v to generate tne riie youtput Examine youtput to find parser states Witn coniicts Foreach sucn state examine tne iterns to nuure wnp tne conriictis occurring t Transform the grammarto eliminate the conflict Rezsnn 1m cnnlllcl pussthie lizan Irznstnrmallnn Ampieuiw Witn uperaters in expressiens Specnv assuciatN vi pveceuence my actiuri Muveuie ateen Ii Muve tne mienuine sewn lE actiuri b b b Turing Machines as a Computer A function f 2 gt 2 is computable if some TM M exists which on every input 10 halts with fw on the tape TM for a computable function halts on every input like Turing deciders Example All usual arithmetic functions on integers are computable 77171 l gt 771 71 77171 l gt 771 96 71 77171 l gt 771 Using recursion and subroutines lelsm Campmatmnrp 215 22c131 Limits of Computation Hantao Zhang httpwwwcsuiowaeduthhangclal The University of Iowa Department of Computer Science Mapping and Turing Reducibilities lensatcampmatmnrp ms b b Mapping Reducibility To reduce a problem A to a problem B by mapping reducibility means to find a computable function f A gt B called a reduction that converts instances of A into instances of B such that for any 10 E 2 w E A iff fw E B Computable functions may be transformations of machine descriptions A computable function f may take an input w where w is an encoding of a TM M ie w M and may return the description of anotherTM ltM fw lelsm Campmatmnrp ms More Examples lmnl Ml 3 llogmnl lensatcampmatmnrp ans Application Some Known Results l l 7 Proof ofthe undecidability of PCP contains two mapping Theorem 522 lfA gm B and B is decidable then A is reductions decidable 9 ATM gm MPOP by f1 ATM a MPOP Corollary 523 lfA gm B and A is undecidable then B 9 MPOP gm POP by f2 MPOP gt POP 395 undec39dab39e ATM lt POP by f f2f1ltM w 1 Theorem 528 lfA gm B and B is Turingrecognizable then A is Turingrecognizable Corollary 529 lfA gm B and A is not Turingrecognizable then B is not Turingrecognizable b lelsm Campmatmnrp ans lensmcampmatmnrp ans Intuitive Meaning of Reducibility Problem 522 7 V Show that A is Turingrecognizable iff A gm ATM 7 Consider two languages ATM and ATM 0 Intuitively they are reducible to each other because a solution to either could be used to solve the other by simply reversing the answer 0 However we know that ATM is not mapping reducible to ATM because ATM is Turing recognizable but ATM is not lelsm Campmatmnrp ans lensmcampmatmnrp ms Example Consider an oracle for ATM 1 An oracle TM with an oracle for ATM can decide more languages than an ordinary TM can 5 Such a TM can obviously decide ATM itself by querying the oracle about its input b Such a TM can also decide ETM with the following procedure TATM Limilsaicampmmmn rpm15 Turing Reducibility Definition 618 An oracle for a language B is an external device that is capable of reporting whether a string 10 is a member of B Informally an oracle for B is a hypothetical decider for B Oracle TM is a modified TM that has the additional capability ofquerying an oracle Notation MB is an oracle TM for language B Limnsaicampmmmnrp ans De nition 620 Language A is Turing reducible to language B A T B ifA is decidable relative to B Example We have shown that ETM T ATM Note Turing reducibility satisfies our intuitive concept of re ducibiity Limilsaicampmmmn 411215 r Procedure TATM TATM On input M where M is a TM 1 Construct the following TM N N On any input a Run M in parallel on all strings in 2 b If M accepts any ofthese strings acceptquot 2 Query the oracle to determine whether N 0 6 ATM 3 fthe oracle answers NO accept ifanswers is YES rejectquot We say that ETM is decidable relative to ATM Limnsai Computatioan ms Note Theorem 621 Turing reducibility is a generalization of mapping lfA T B and B is decidable then A is decidable reducibility quotA Sm B then A ST B because the mapping reduction Proof If B Is deCIdable then we may replace the oracle for B may be used to give an oracle TM that decide A relative by an actual procedure that decide B Thus we may replace to B39 the oracle TM that decides A by an ordinary TM that decides 0 An oracle TM with an oracle for ATM can solve problems that are not solvable by ordinary TM A However oracle Turing machines cannot decide all languages Problem 64 Problem 64 r Let A nM M u l M is an oracle TM and MATM accepts 10 Show that ATM is undecidable relative to ATM lensm Campmatianrp 1515 1 N Midterm I 22C2131 Spring 2009 300 points7 55 minutes7 open book and notes7 no computers 50 Suppose the input le contains many binary strings Please provide a complete leX le which will produce a C program that counts how many strings of the input le are in L1 w E 0 1 lw has odd number of 17s Sample solution M int goodnum O badnum O 70 O1O101O goodnum 011 badnum I tn 730 main yylexo printf of good binary strings quotod of bad strings dnquot goodnum badnum 50 A palindrome is a string that reads the same forward and backward For instance7 010 is a palindrome but 001 is not Please provide a context free grammar for L2 w 6 00 10 l w is a palindrome Sample solution G SA01PS where P is Sam A 0A0l1A1l0l1le

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.