New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Allie West II


Allie West II

GPA 3.51


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 81 page Class Notes was uploaded by Allie West II on Thursday October 29, 2015. The Class Notes belongs to CSCI 3434 at University of Colorado at Boulder taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231996/csci-3434-university-of-colorado-at-boulder in ComputerScienence at University of Colorado at Boulder.

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
CSCI 3434 Theory of Computation Class Notes Spring 2002 Karl Winklmann Carolyn J C Schauble Department of Computer Science University of Colorado at Boulder January 177 2002 2002 Karl VVinklmann7 Carolyn l C Schauble Preface Unlike most textbooks on theory of computation these notes try to build as much as possible on knowledge that juniors or seniors in computer science ten to have For example the introduction of undecidability issues in the first chap ter starts with examples of programs that read and process other programs that are familiar to the students Unix utilities like grep cat or diffi As another example the proof of Cook7s Theorem NPcompleteness of Boolean satisfiabil ity C0071 is done in terms of compilation instead of the usual approach of turning a nondeterministic Turing machine into a Boolean expression we com pile a nondeterministic C program into machine language and the resulting circuit satisfiability problem into the problem of determining satisfiability of Boolean expressionsi All material is presented without unnecessary notational clutteri To get to strong results quickly the text starts with the machine model students already know as plain programsi When a proof requires a substantial new concept the concept is first pre sented in isolation For example before we prove that all problems in P can be transformed into SAT we show transformations for a few concrete exam ples This allows the students to understand the concept of transformation into Boolean expressions before we present the generic argument that covers a whole class of such transformationsi Pedagogically this makes sense even though the examples get superseded quickly by the more general result Students should know the basic concepts from a course on algorithms including the different types of algorithms greedy diVide andconquer etc and they should have some understanding of algorithm design and analysis and of basic concepts of discrete mathematics such as relations functions and Boolean op erations lntroductions to such concepts can of course be found in many books eigi Sch96 or Dea96li These notes are not meant for selfstudyi The concepts are often too subtle and these notes are generally too terse for that They are meant to be read by students in conjunction with classroom discussion Karl Winklmann Carolyn Schauble Boulder January 2002 What is different Prerequisites Don t try this at home Contents H O CO g Computability lil Strings7 Properties7 Programs i i i i i i i i i i i i i i i i i i i i 12 A Proof By Contradiction i i i i i i i i i i i i i i i i i i i i i i 13 A Proof of Undecidability i i i i i i i i i i i i i i i i i i i i i i 14 Diagonalization i i i i i i i i i i i i i i i i i i i i i i i i i i i i 15 Transformations 16 The Undecidability of All lOProperties i i i i i i i i i i i i i i 1 7 The Unsolvability of the Halting Problem i i i i i i i i i i i i i 18 Godel7s lncompleteness Theorem i i i i i i i i i i i i i i i i i i FiniteState Machines 21 State Transition Diagrams i i i i i i i i i i i i i i i i i i i i i i 22 The Myhill Nerode Theorem 23 Programs That Process FiniteState Machines i i i i i i i i i i i 24 The Pumping Lemma for Regular Languages i i i i i i i i i i i ContextFree Languages 31 ContextFree Grammars i i i i i i i i i i i i i i i i i i i i i i i 32 Parsing 33 The Pumping Lemma for ContextFree Grammars 34 A Characterization of ContextFree Languages Time Complexity The State of Knowledge Before NPCompleteness i i i i i i i i i NP l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l The NP completeness of SATISFIABILITY l l l l l l l l l l l l l i More NPComplete Problems i i i i i i i i i i i i i i i i i i i The Holy Grail P NP i i i i i i i i i i i i i i i i i i i i i 41 4 2 4 3 4 4 45 Bibliography CONTENTS Chapter 1 Computability We write programs in order to solve problems But if a problem is 77too hard77 and our program is 77too simple77 this won t work The sophistication of our program needs to match the intrinsic difficulty of the pro lemi Can this be made precise Theory of computation attempts just that We will study classes of programs trying to characterize the classes of problems they solve The approach is mathematical we try to prove theoremsi In this rst chapter we do not place any restrictions on the programs later we will restrict the kinds of data structures the programs use Maybe surprisingly even without any restrictions on the programs we will be able to prove in this rst chapter that many problems cannot be solved The central piece of mathematics in this rst chapter is a proof technique called proof by contradiction The central piece of computer science is the notion that the input to a program can be a programi 11 Strings Properties Programs Programs often operate on other programs Examples of such tools are edi tors compilers interpreters debuggers utilities such as 7 to pick some Unix examples 7 diff lint rcs grep cat more and lots of others Some such programs determine properties of programs they are operating on For example a compiler among other things determines whether or not the source code of a program contains any syntax errorsi Figure lil shows a much more modest example The program oddlengthxpp determines whether or not its input consists of an odd number of characters If we ran the program in Figure ill on some text le eg by issuing the two comman s CC 0 oddlength oddlengthcpp oddlength lt phonelist the response would be one of two words Yes or No assuming that the program 8 CHAPTER 1 COMPUTABILITY void main void if oddlength cout ltlt quotYesquot else cout ltlt quotNoquot 339 boolean oddlength void boolean toggle FALSE while getchar EOF toggle toggle 339 return toggle Figure iii A program oddlengthxpp that determines whether or not its input consists of an odd number of characters was stored in oddlength cpp and that there was indeed a text le phonelist and that this all is taking place on a system on which these commands make sense1i We could of course run this program on the source texts of programs7 even on its own source text CC 0 oddlength oddlengthcpp oddlength lt oddlengthcpp The response in this case would be No because it so happens that the source code of this program consists of an even number of characters Mathematically speaking7 writing this program was a constructive proof of the following theoremi To show that there was a program as claimed by the theorem we constructed onei Theorem 1 There is a program that outputs Yes or No depending on whether or not its input contains an odd number of characters Equivalently there is a boolean function that returns TRUE or FALSE depending on whether or not its input2 contains an odd number of characters In theory of computation the word decidable is used to describe this sit uation7 as in 1For our examples of programs we assume a Unix environment and a programming language like C or C To avoid clutter we leave out the usual include and def ine statements and assume that TRUE and FALSE have been de ned to behave the way you would expect them to 2The input to a function is that part of the stande input to the program that has not been read yet at the time the function gets called H H STRINGS PROPERTIES PROGRAMS 9 void main void char 0 c getcharo while 0 EOF while 0 7X7 loop forever if an X is found c getcharo Figure 12 A program x cpp77 that loops on some inputs Theorem 1 new wording Membership in the set LODDLENGTH I z is odd is decidable The notion of a property is the same as the notion of a set I haVing property H is the same as I being in the set 2 z 2 has property H This suggests yet another rewording of Theorem 1 which uses standard terminology of theory of computation If we use the name ODDLENGTH for the property of consisting of an odd number of characters then the theorem reads as follows Theorem 1 yet another wording ODDLENGTH is decidable Concern about whether or not a program contains an odd number of characters is not usually uppermost on programmers7 mindsi An example of a property of much greater concern is whether or not a program might not always terminatei Lets say a program has property LOOPING if there exists an input on which the program will not terminatei Two examples of programs with property LOOPING are shown in Figures 12 and 13 In terms of sets haVing property LOOPING means being a member of the set LLOOPING z z z is a syntactically correct program and there is an input y such that I when run on y will not terminate Instead of being concerned with whether or not there is some input among the infinitely many possible inputs on which a given program loops let us simplify matters and worry about only one input per program Letls make that one input the source code of the program itself Let SELFLOOPING be the property that a program will not terminate when run with its own source text as input In terms of sets SELFLOOPING means being a member of the set LSELFLOOPING z z z is a syntactically correct program and when run on I will not terminate The programs in Figures 12 and 13 both have this property The program in Figure 11 does not The bad news about SELFLOOPING is spelled out in the following theoremi Theorem 2 SELFLOOPING is not decidable Properties vs sets More interesting properties of programs St rings vs programs CHAPTER 1 COMP UTABILITY void main void while TRUE 339 Figure 13 Another program uselesscpp that loops on some in fact all inputs What this means is that there is no way to write a program which will print quotYesquot if the input it reads is a program that has the property SELFLOOPING and will print quotNoquot otherwise Surprising maybe but true and not even very hard to prove as we will do a little later in Section 13 which starts on page 12 The de nitions of LOOPING and SELFLOOPING use the notion of a syntactically correct programi77 The choice of programming language does not matter for any of our discussions Our results are not about peculiarities of somebodyls favorite programming language they are about fundamental aspects of any form of computation In fact to mention syntax at all is a red herring We could do all our programming in a language let s call it C77 in which every string is a programi If the string is a C or C Program we compile it with our trusty old C or C compileri If not we compile it into the same object code as the program main 77 Then every string is a program and running I on y now makes sense for any strings I and y It means that we store the string 1 in a le named say xcmm and the string y in a le named say y and then we use our new C77 compiler and do CC o x xcmm x lt y So lets assume from now on that we are programming in C77 and thus avoid having to mention syntactically correct77 all the time One convenient extension to this language is to regard Unix shell constructs like grep Boulder I sort as programs This program can be run on some input by cat phonebook I grep Boulder I sort grep Boulder phonebook I sort or by grep Boulder I sort lt phonebook 12 A PROOF BY CONTRADICTION 11 12 A Proof By Contradiction Before we prove our rst undcidability result here is an example that illustrates the technique of proving something by contradiction Proving a theorem by contradiction starts with the assumption that the theorem is not true From this assumption we derive something that we know is not true The conclusion then is that the assumption must have been false the theorem true The something that we know is not true often takes the form of A and not A77 Theorem 3 is irrational A rational number is one that is equal to the quotient of two integers An irrational number is one that is not rational Proof Pythagoreans7 5th century BC 3 For the sake of deriving a con tradiction assume that J is rationali Then 2 3 11 for two integers p and L which have no factors in common they are relatively primer77 Squaring both sides of 11 yields 2 Ii 12 and therefore 2 X g p2 13 This shows that p2 contains a factor of 2 But p2 cannot have a factor of 2 unless p didi Therefore p itself must contain a factor of 2 which gives p2 at least two factors of 2 p22gtlt2gtlt7quot 14 for some integer Ti Combining 1 3 and 14 yields 2Xq22gtlt2gtlt39r 15 which simpli es to q 2 X T 16 which shows that 4 also contains a factor of 2 contradicting the fact that p and L were relatively primer D Next we apply this proof technique to get our rst undecidability resulti 3according to Kline Mathematical Thought from Ancient t0 Modem Times New York 1972 pp3273 12 CHAPTER 1 COMPUTABILITY void main void if selflooping stop don t loop else while TRUE do loop forever boolean selflooping void returns TRUE if the input is a program which w en run with its own source code as input does not terminate FALSE otherwise Figure 14 A program diagonalxpp that would exist if SELFLOOPING were decidable 13 A Proof of Undecidability Proof of Theorem 2 For the sake of deriving a contradiction assume that there is a programs that decides if its input has property SELFLOOPINGi If such a program existed we could rewrite it as a function boolean selfloopingO that decides whether or not its input has property SELFLOOPINGi We could then write the program diagonal4 shown in Figure 14 Does the program in Figure 14 itself have property SELFLOOPING Claim 1 It does not Proof of Claim 1 Assume it did Then when running the program with its own source code as input the function selflooping would return TRUE to the main program making it terminate and hence not have property SELFLOOPING a contradiction El Claim 2 It does Proof of Claim 2 Assume it did not Then when running the program with its own source code as input the function selflooping would return FALSE to the main program sending it into an in nite loop and hence have property SELFLOOPING a contradiction I These two claims form a contradiction proving our initial assumption wrong there cannot be a program that decides if its input has property SELFLOOPINGi D 4W39hy diagonal is a tting name for this program will become clear in the next section 14 DIAGONALIZATION 13 digits A numbers i L i i i i i 10 100 103 104 105 106 107 108 d 0 1 1 9 1 1 9 9 9 7 1 7 0 Q 2 8 4 1 1 0 4 T2 0 0 8 8 4 1 1 3 8 T3 0 8 4 1 1 0 8 4 1 7 4 0 1 0 0 Q 0 1 0 0 7 5 0 0 9 9 9 Q 0 9 9 7 5 0 0 4 6 2 6 1 4 6 7 7 0 1 1 0 0 2 1 1 0 0 4 4 9 4 3 4 4 1 Figure 115 The diagonal in the proof of Theorem 4 14 Diagonalization The proof of Theorem 2 was a special kind of proof by contradiction called a diagonalization proofi77 To understand that that aspect of the proof7 let s look at a classical theorem with a diagonalization proofi Theorem 4 Cantor7 1873 The Teal numbeTs we not countable A set is countable if there is a function from the natural numbers onto the set In other words7 there is a sequence T1T2T3T4T5Hi that contains all members of the set Proof Cantor7 18901891 5 Assume the real numbers are countablei en there is a sequence that contains all reals and a subsequence T17 T27 T37 i i i that contains all reals from the interval 07 1 Consider the in nite matrix that contains in row i a decimal expansion of Ti one digit per columni See Figure 115 for an illustration Consider the number d whose i h digit is 9 if the matrix entry in row i and column 239 is 17 and whose i h digit is 1 otherwise The number d thus de ned differs from every number in the sequence T17 T27 T37 i i i contradicting the assumption that all reals from 01 were in the sequencer6 El 5Cantor gave a different rst proof in 1873 according to Kline p997 6There is a subtlety in this proof stemming from the fact that two different decimal ex pansions can represent the same number 010000 N 009999 V V V Why is this of concern And why is the proof ok anyway Other proof techniques Heuristics CHAPTER 1 COMP UTABILITY programs used as inputs A programs P1 P2 P3 P4 P5 P6 P7 P8 diagonal 1 1 0 1 1 0 0 0 pl 9 0 0 0 1 1 0 0 pg 0 Q 0 0 1 1 0 0 pg 0 0 l 1 0 0 0 1 p4 1 0 0 Q 0 1 0 0 p5 0 0 0 0 Q 0 0 0 pp 0 0 0 0 0 l 0 0 p7 1 1 0 0 0 1 l 0 0 0 0 0 0 0 0 1 P3 Figure 116 The diagonal in the proof of Theorem 2 How does this proof of Cantor s Theorem relate to our proof of Theorem 2 Programs are nite strings and hence countable Let 101102 1031 1 i be a sequence of all programs Unlike a sequence of all reals such a sequence does exist since programs are nite stringsi Consider the in nite boolean matrix which has a 0 in row i and column j if program i when run with the source code of program j as input does not terminate and a 1 if it does See Figure 16 for an illustration The program diagonal cpp of Figure 114 which we assumed to exist at the start of the proof of Theorem 2 then differs from each program in the sequence contradicting the fact that all programs were in the sequence The reason is that if program pi does terminate on input pi then diagonalcpp does not terminate on input 17 and vice versa It is remarkable that without diagonalization nobody would know how to prove eorem 2 nor any oft e other undecidability results in this chapter This monopoly of one proof technique will cause problems in the study of computational complexity in Chapter 4 which injects a concern about efficiency into the discussion Diagonalization does not work nearly as well in that context Without any other technique available we will not be able to prove some very basic conjecturesi Every computational problem whether unsolvable in theory or not is open to a heuristic approach The theory presented here does not address the feasibility of heuristic methods It does suggest that heuristics would be the way to go if one wanted to create software tools to solve in some practically useful sense any of the problems which this theory shows unsolvable 15 TRANSFORMATIONS Digressing for a moment from our focus on what programs can and cannot do programs that process programs are not the only example of selfreferencing causing trouble and far from the oldest one Here are a few others An example known to Greek philosophers over 2000 years ago is the self referencing statement that says This statement is a lie This may look like a pretty silly statement to consider but it is true that the variant that says This is a theorem for which there is no proof underlies what many regard as the most important theorem of 20thcentury mathematics Godells lncompleteness Theorem More on that in Section 18 on page 25 A seemingly nonmathematical example arises when you try to compile a Catalog of all catalogs which is not a problem yet but what about a Catalog of all those catalogs that do not contain a reference to themselves Does it contain a reference to itself If we call catalogs that contain a reference to themselves selfpromoting the trouble stems from trying to compile a catalog of all nonselfpromoting catalogs Note the similarity to considering a program that halts on all those programs that are sel oopingi 15 Transformations SELFLOOPING is not the only undecidable property of programs To prove other properties undecidable we will exploit the observation that they have strong connections to SELFLOOPING connections such that the undecidability of SELFLOOPING rubs off on them Speci cally we will show that there are transformations of SELFLOOPING into other problems Before we apply the concept of transformations study of undecidability let s look at some examples of transformations in other set tings Consider the Unix command to our sort It can be used like sort lt phonebook to sort the contents of a le sort solves a certain problem called SORTING a problem that is so common and important that whole chapters of books have been written about it and a solution comes with every computer system you might want to buy But what if the problem you want to solve is not SORTING but the prob lem known as SORTING THOSE LINES THAT CONTAIN THE WORD Boulder STLTCTWB for short You could write a program stltctwb to solve STLTCTWB and use the program like stltctwb lt phonebook Selfreference in other domains Solvable or decidable Transforming binary addition into Boolean satis ability SAT 16 CHAPTER 1 COMPUTABILITY But probably you would rather do cat phonebook I grep Boulder I sort This is an example of a transformation The command grep Boulder transforms the STLTCTWB problem into the SORTING problemi The command grep Boulder I sort solves the STLTCTWB problemi The cat phonebook I merely provides the input The general pattern is that if b is a program that solves problem B and aJ ob I b solves problem A then aJ ob is called a transformation of problem A into problem 3 The reason for doing such transformations is that they are a way to solve problems If we had to formulate a theorem about the matter it would read as follows Letls make it an Observation That way we donlt have to spell out a proo I Observation 1 If there is a program that transforms problem A into problem B and there is a program that solves problem B then there is a program that solves problem A Since at the moment we are more interested in proving that things cannot be done than in proving that things can be done the following rephrasing of the above observation will be more useful to us A problem is solvable if there exists a program for solving it Observation 2 If there is a program that transforms problem A into problem B and problem A is unsolvable then problem B is unsolvable as well In good English problems get solved and questions get decidedi Fol lowing this usage we speak of solvable and unsolvable problems and de cidable and undecidable questions For the substance of our discussion this distinction is of no consequence For example solving the SELFLOOPING prob lem for a program I is the same as deciding whether or programs have the property SELFLOOPINGI In either case the pre x un means that there is no program to do the job For another example of a transformation consider the following two problems Let BINARY ADDITION be the problem of deciding given a string like 1011011 1 7 15 TRANSFORMATIONS 17 whether or not it is a correct equation between binary numbers This one isnlti Let7s restrict the problem to strings of the form 12 11 92 91 23 22 21 1 8 with each Ii yi and 2139 being 0 or 11 Lets call this restricted version 2 ADD1 Let Boolean Satis ability SAT be the problem of deciding given a Boolean expression whether or not there is an assignment of truth values to the variables in the expression which makes the whole expression true A transformation of 2 ADD 750 SAT is a function t such that for all strings a7 1 represents a correct addition of two binary numbers 42gt ta is a satis able Boolean expressioni How can we construct such a transformation Consider the Boolean circuit in Figure 1171 It adds up two 2bit binary numbersi Instead of drawing the picture we can describe this circuit equally precisely by the Boolean expression 12 A 92 gt 53 Cg 69 2g 42gt 22 Cg 2g 42gt cg 03 V 5 42gt 23 gtgtgtgtgtgt VVVVVVV This suggests transformation of 2 ADD to SAT that maps the string 17 to the expression 0 ED 1 ltgt 1 0 1 ltgt Cg 1 ED 1 ltgt 2g 1 1 ltgt 5 3 Cg ED 2 ltgt 1 Cg 2g 42gt cg ltlt v gt gt o gt which appropriately is not satis ablei There are four variables to choose values for 52 22 53 an 0 ut no choice of values for them will make the whole expression truer Note that every single one of the seven conjuncts can be made true with some assignment of truth values to 52 2 53 and 0 but not all seven can be made true with one and the same assignmenti In terms of the circuit this means that if the inputs and outputs are xed to re ect the values given in 117 at least one gate in the circuit has to end up with inconsistent values on its input and output wires or at least one wire has to have different values at its two ends The circuit is not satisfiablei77 CHAPTER 1 COMP UTABILITY x1 Y1 x2 Y2 Figure 17 A Circuit for adding two 2bit binary numbers H 5 TRANSFORMATIONS Figure 18 A graph of activities and con icts Note that transformations do not always go from a harder problem to an easier one7 In fact the opposite is closer to the truth The destination problem can be easier than the source problem only to the extent of the computational effort expended in carrying out the transformation But the destination problem can be much harder than the source problemi For example you can transform ODDLENGTH to LOOPING but not LOOPING to ODDLENGTHi Graphs like the one shown in Figure 18 can be used to represent scheduling problems Each node represents an activity eg a meeting of some group and an edge between two nodes means that the two activities must not be schedule at the same time eg because there is a person who needs to attend both Since activities a b and e are all con icting with each other there is no way to schedule all the activities into fewer than three time slots Are three slots enough Instead of activities being scheduled into time slots graph theorists talk about nodes being colored T e question then becomes are three different colors enough to color all the nodes without adjacent nodes getting the same color This problem is known as GRAPH 3 COLORABILITY or 3 COLOR for short The idea behind the transformation is to make the variable aGREEN aRED aBLUE true if and only if the vertex a gets colored green red blue The statement that a and I get different colors can then be made in the language of Boolean expressions as aGREEN A bGREEN A aRED A bRED A aBLUE A bBLUE 19 We need to make one such statement for each of the nine edges in the graph The 7 Harder and easier mean needing more and less of a computational resource Most often the resource we care about is computing time Harder and easier do not mean harder or easier to program Programming e ort is not addressed by this theory Transforming GRAPH 3 COLORABILITY into SAT Editing programs 20 CHAPTER 1 COMP UTABILITY conjunction of these nine statements does not yet complete the transformation because it could always be satis ed by making all the variables false a choice that corresponds to avoiding color con icts by not coloring the nodes at alli We can complete the transformation by insisting that each node get exactly one color assigned to it For node a this can be done by the expression aGREEN Am Am V m A aRED A m V m A m A aBLUE 110 In general to carry out the transformation for any graph G CV E we just have to make a statement like 110 for every node of the graph and a statement like 19 for every edge ie we have to write this expression Ea IGREENAIRED AIBLUE VIGREENAIRED AIBLUE VIGREENAIRED AIBLUE 16V IGREENAyGREEN A IRED AyRED A IBLUE AyBLUE gty6E This expression Ea is satis able if and only if the graph G is 3colorablei To make Observation 2 useful for proving undecidability results we need to nd transformations from one property of programs into another Lemma 1 There is a program edit which given as input a program 1 creates as output a program y with the following two properties 1 y never reads any input and 2 y on any input which it ignores i see previous item runs like I would on input 1 Proof We can achieve this transformation by hand77 in a session with our fa vorite text editor As an example if we start with I being the program x cpp77 from Figure 12 we could create the program in Figure 110 We can even do this in a way where the editing commands do not depend on the program I that is being editingi Therefore we could take a copy of the editor and hardcode those commands into it or preferably and equivalently put the commands into a script le77 or a macro77 for our editor3i D 8Better yet we can simplify this editing task greatly by making y the oneline program x lt xcpp which has all the right properties To see that it ignores its input do x lt xcpp lt input 16 THE UNDECIDABILITY OF ALL IU PROPERTIES 21 void main void xonxnoinput O 339 void xonxnoinput void runs like 2 but 39C instead of reading input it reads 339 from a string constant Figure 19 The result of editing program x 16 The Undecidability of All IOProperties Recall that LOOPING is the property that there exists an input on which the program will not terminate Theorem 5 LOOPING 239s undecidable Proof The program edit of Lemma 1 transforms SELFLOOPING into LOOP INGl By Observation 2 this proves LOOPING undecidablel I What other properties of programs are often of interest The prime consider ation usually is whether or not a program works correctly77 The exact meaning of this depends on what you wanted the program to do If you were working on an early homework assignment in Programming 101 working correctly77 may have meant printing the numbers 1 2 3 l l l 10 Let ONE TO TEN be the problem of deciding whether or not a program prints the numbers 1 2 3 10 Theorem 6 ONE TO TEN 239s undecidable Proof Figure llll illustrates a transformation of SELFLOOPING into the nega tion of property ONE TO Note that unlike the function xonxnoinput in the previous proof the function xonxnoinputmooutput suppresses whatever output the program x might have generated when run on its own source code as input This is necessary because otherwise the transformation would not work in the case of programs x that print the numbers 1 2 3 l l l 10 Since the negation of ONE TO TEN is undecidable so is the property ONE TO TENl D How many more undecidability results can we derive this way Figure 113 shows an example of an inputoutput table77 1075 of a program I For every input the table shows the output that the program producesl If the program loops forever on some input and keeps producing output the entry in the righthand column is an infinite stringl 2 CHAPTER COMPUTABHJTY define EOF NULL NULL is the proper end marker since we are reading from a string void main void xonxnoinput char mygetchar void static int i 0 static char inputstri ng start of input string II n void main void n n char cn c getcharn while 0 EOFn n while 0 7X7 loop forever if an X is foundn c getcharn n n end of input string return inputstringi void xonxnoinput void char 0 c mygetchar while 0 EOF while 0 7X7 loop forever if an X is found c mygetchar Figure 110 The result of editing the program xcpp of Figure 12 16 THE UNDECIDABILITY OF ALL IO PROPERTIES 23 void main void xonxnoinputnooutput onetoten void xonxnoinputnooutput void runs like x but instead of reading input it reads from a string constant and it does not generate any output void onetoten void int i for i 1 i lt 10 i cout ltlt i ltlt endl Figure 111 Illustrating the proof of Theorem 6 void main void xonxnoinputnooutput notPI void xonxnoinputnooutput void runs like a program that does not have property PI void notPI void 39C Figure 112 The result of the editing step rice on input x 24 CHAPTER 1 COMP UTABILITY Inputs Outputs A Empty input file 0 Okay 1 00 Yes 01 Yes Yes Yes 10 No 11 000 Yes No Yes No Yes No 001 Segmentation fault 010 Core dumped Figure 113 The inputoutput function of a lousy program These tables are not anything we would want to store nor do we want to compute them in any sense They merely serve to de ne what an input output property is lnformally speaking7 a property of programs is an input output property if the information that is necessary to determine whether or not a program I has the property is always present in the programs inputoutput table 10 For example7 the property of making a recursive function call on some input7 letls call it RECURSIVE7 is not an inputoutput property Even if you knew the whole inputoutput table such as the one in Figure 1137 you would still not know whether the program was recursivei The property of running in linear time is not an inputoutput property7 nor is the property of always producing some output within execution of the first one million statements7 nor the property of being a syntactically correct C programi Examples of inputoutput properties inclu e o the property of generating the same output for all inputs7 o the property of not looping on any inputs of length less that 10007 0 the property of printing the words Core dumped on some input More formally7 a property H of programs is an inputoutput property if the following 1s true For any two programs a and 127 if IOa 105 then either both a and b have property 117 or neither does A property of programs is trivial if either all programs have it7 or if none doi Thus a property of programs is noutn39vz39al if there is at least one program that has the property and one that doesnt9 9There are only two trivial properties of programs One is the property of being a program 17 THE UNSOLVABILITY OF THE HALTIN G PROBLEM 25 Theorem 7 Rice s Theorem No nontrivial inputoutput property of pro grams is decidable Proof Let H be a nontrivial inputoutput property of programs There are two possibilities Either the program main while TRUE 111 has the property H or it doesnt Letls rst prove the theorem for properties H which this program 111 does have Let notPI be a function that runs like a program that does not have property Hi Consider the program that is outlined in Figure 112 It can be created from I by a program call it rice much like the program in Figure 19 was created from I by the program edit of Lemma 1 The function rice transforms SELFLOOPING into H which proves H unde cidablei What if the in niteloop program in 111 does not have property H In that case we prove Ricels Theorem for the negation of H 7 by the argument in the rst part of this proofi and then observe that if the negation of a property is undecidable so is the property itself D 17 The Unsolvability of the Halting Problem The following result is probably the bestknown undecidability result Theorem 8 Unsolvability of the Halting Problem There is no program that meets the following speci cation When given two inputs aprogram z and a string y print Yes if I when run on y terminates and print No otherwise Proof Assume HALTING is decidablei llei assume there is a program halting which takes two le names x and y as arguments and prints Yes if x when run on y halts and prints No otherwisei Then SELFLOOPING can be solved by running halting with the two arguments being the same and then reversing the answer ilel changing Yes to No and vice versa 18 Godel s Incompleteness Theorem Once more digressing a bit from our focus on programs and their power it is worth pointing out that our proof techniques easily let us prove what is certainly the most famous theorem in mathematical logic and one of the most famous in i all programs have that property The other is the property of not being a program i no program has that property In terms of sets these are the set of all programs and the empty set 26 CHAPTER 1 COMP UTABILITY all of mathematics The result was published in 1931 by Kurt Godel and put an end to the notion that if only we could nd the right axioms and proof rules we could prove in principle all true conjectures Put another way it put an end to the notion that mathematics could somehow be perfectly automated Theorem 9 Godel s Incompleteness Theorem 193110 For any system of formal proofs that includes at least the usual axioms about natural numbers there are theorems that are true but do not have a proof in that system Proof If every true statement had a proof SELFLOOPING would be decidable by the following algorithmi For any given program I the algorithm generates all strings in some system atic order until it nds either a proof that I has property SELFLOOPING or a proof that I does not have property SELFLOOPINGi D It is crucial for the above argument that veri cation of formal proofs can be automated iiei done by a programi It is not the veri cation of formal proofs that is impossible What is impossible is the design of an axiom system that is strong enough to provide proofs for all true conjectures Does this mean that once we choose a set of axioms and proof rules our mathematical results will forever be limited to what can be proven from those axioms and rules Not at all The following lemma is an examp ei Lemma 2 For any system of formal proofs the program in Figure 114 does have property SELFLOOPING but there is no formal proof of that fact within the system Proof The program in Figure 114 is a modi cation of the program we used to prove SELFLOOPING undecidablei Now we prove SELFLOOPING unprovablei When given its own source as input the program searches systematically for a proof that it does loop and if it nds one it terminates Thus the existence of such a proof leads to a contradiction Since no such proof exists the program keeps looking forever and thus does in fact have property SELFLOOPINGi CI Note that there is no contradiction between the fact that there is no proof of this program having property SELFLOOPING within the given axiom system and the fact that we just proved that the program has property SELFLOOPINGi It is just that our informal proof cannot be formalized within the given systemi W at if we enlarged the system for example by adding one new axiom that says that this program has property SELFLOOPING Then we could prove that fact with a oneline proof no less This is correct but note that the program had the axiom system hard coded77 in it So if we change the system we get a new program and the lemma is again true 7 for the new programi 1OKult Godel Uber formal unentscheidbare Satze der Principia Mathematica und Vere wandter Systems I Monatshefte fiir Mathematik und Physik 38 1931 173798 GODEL S IN COMPLETENESS THEOREM 27 H 00 void main void systematically generates all proofs in the proof system under consideration and stops if and when it finds a proof that its input has property SELFLUOPING Figure 114 Illustrating the proof of Lemma 2 Exercises Ex 11 The rational numbers are countable as argued in class Why does Diagonalization the diagonalization proof that shows that the real numbers are not countable not work for the rational numbers Ex 12 Let SELFRECURSIVE be the property of programs that they make a recursive function call when running on their own source code as input De scribe a diagonalization proof that SELFRECURSIVE is not decidable Ex 13 Describe a transformation from SELFLOOPING to the property of Transformations not reading any input Ex 14 The function edit that is used in the proof of Theorem 5 transforms SELFLOOPING not only to LOOPING but also to other properties Give three such properties Ex 15 Consider the following problem Given a graph7 is there a set of edges so that each node is an endpoint of exactly one of the edges in that set Such a set of edges is called a 77complete matching Describe a transformation of this problem to the satis ability problem for Boolean expressions You may do this by showing and explaining7 if it s complicated the expression for one of the above graphs Ex 16 If G is a graph that you are trying to find a 3coloring for7 if tG is the Boolean expression the graph gets translated into by our transformation of 3 COLOR into SAT7 and7 finally7 if someone handed you an assignment of truth values to the variables of tG that satisfied the expression7 describe how you can translate that assignment of truth values back to a 3 coloring of the graph Ex 17 Consider trying to transform 3 COLOR into SAT but using7 in place of aGREEN A aRED A aBLUE V aGREEN A aRED A aBLUE V aGREEN A aRED A aBLUE 28 CHAPTER 1 COMP UTABILITY the expression IGREEN V IRED V IBLUE 1 Would this still be a transformation of 3 COLOR into SAT Explain why7 or why not 7 Could we still translate a satisfying assignment of truth values back into a 3coloring of the graph Explain how7 or why not Ex 18 a Transform SELFLOOPING into the property of halting on those inputs that contain the word Halt7 and looping on all others 7 What does this prove Ex 19 a Transform ODDLENGTH into SELFLOOPING b What does this prove IOProperties Ex 110 Give three undecidable properties of program that are not input output properties and that were not mentioned in the notes Give three others that are nontrivial lO properties7 hence undecidable7 but were not mentioned in c ass Ex 1 11 We needed to suppress the output in the xonxnoinputmooutput function used in the proof of Ricels Theorem Which line of the proof could oth erwise be wrong Ex 112 ls SELFLOOPING an inputoutput property More Undecidability Ex 113 Formulate and prove a theorem about the impossibility of program esults optimization Ex 114 Autograders are programs that check other programs for cor rectness For example7 an instructor in a programming course might give a programming assignment and announce that your programs will be graded by a program she wrote What does theory of computing have to say about this Choose one of the three answers below and elaborate in no more than two or three short sentences 1 Autograding is not possible 2 Autograding is possible 3 It depends on the programming assignment Ex 115 Which of the following ve properties of programs are decidable Which are lOproperties 101f having a choice is not acceptable in a real algorithm we can always program the algorithm to prefer RED over GREEN over BLUE 200 pomw g GODEL S IN COMPLETENESS THEOREM i Containing comments i Containing only correct commentsi Being a correct parser for C iiei7 a program Which outputs 77Yes77 if the input is a syntactically correct C program7 and 77No77 otherwise i Being a correct compiler for C iiei7 a program Which7 When the input is a C program7 outputs an equivalent machinelanguage version of the input 77Equivalent77 means haVing the same 10 table i The output not depending on the input CHAPTER 1 COMP UTABILITY Chapter 2 FiniteState Machines In contrast to the preceding chapter where we did not place any restrictions on the kinds of programs we were considering in this chapter we restrict the programs under consideration very severelyi We consider only programs whose storage requirements do not grow with their inputsi This rules out dynamically growing arrays or linked structures as well as recursion beyond a limited depth The central piece of mathematics for this chapter is the notion of an equiv alence relationi77 It will allow us to arrive at a complete characterization of what these restricted programs can do Applying mathematical induction will provide us with a second complete characterization 21 State Transition Diagrams Consider the program oddlength from Figure ill on page 8 Let7s use a de bugger on it and set a breakpoint just before the getchaIO statement When the program stops for the rst time at that breakpoint we can examine the values of its lone variable The value of toggle is FALSE at that time and the instruction pointer77 is of course just in front of that getchar statementi Let7s refer to this situation as state i If we resume execution and provide an input character then at the next break the value of toggle will be TRUE and the instruction pointer will of course again be just in front of that getchari This is another state the program can be in Letls call it state B Letls give the program another input character The next time our debugger lets us look at things the program is back in state Al As long as we keep feeding it input characters it bounces back and forth between state A and state B What does the program do when an EOF happens to come around From state A the program will output No from state B Yesi Figure 21 summarizes all of this in a picture The double circle means that an EOF produces a Yes the single circle a Not 2 is the set of all possible input 31 The program oddlength once more7 in a picture Terminology Another Example CHAPTER 2 FINITE STATE MACHINES Z Figure 21 The program oddlength as a nitestate machine characters the input alphabet Labeling a transition with 2 means that any input character will cause that transition to be ma e A picture such as the one in Figure 21 describes a nitestate machine or a nitestate automaton States drawn as double circles are accepting states single circles are rejecting statesi lnput characters cause transitions between states Arrows that go from state to state and are labeled with input characters indicate which input characters cause what transitions For every state and every input character there must be an arrow starting at that state and labeled by the input character The initial state or start state is indicated by an unlabeled arrowi1 An input string that makes the machine end up in an accepting rejecting state is said to be accepted rejected by the machine If M is a nitestate machine M then LM z z z is accepted by M is the language accepted by M i Let LMATCH be the language of all binary strings that start and end with a 0 or start and end with a 1 Thus LMATCH 0 l 00 11 000 010 101 111 0000 0010 i i or more formally LMATCH c czc z E 0 lquot c E 0 21 Can we construct a nitestate machine for this language To have a chance to make the right decision between accepting and rejecting a string when its last character has been read it is necessary to remember what the rst character and the last character werei How can a nitestate machine remember or know this information The only thing a nitestate machine knows at any one time is which state it is in We need four states for the four combinations of values for those two characters assuming again that we are dealing only with inputs consisting entirely of 0s an s one of those four states would be appropriate for the machine to be in at the start when no characters have been read yet A fth state will serve as start statei 1Purists would call the picture the transition diagram of the machine and de ne the machine itself to be the mathematical structure that the picture represents This structure consists of a set of states a function from states and input symbols to states a start state a set of accepting states 21 STATE TRANSITION DIAGRAMS 9 1 0 Figure 212 A nitestate machine that accepts LMATCH Now that we know what each state means putting in the right transitions is straightforward Figure 22 shows the nished product Note that we could have arrived at the same machine by starting with the program match in Figure 23 and translating it into a nitestate machine by the same process that we used earlier with the program oddlengthi Consider the language LEQA of all nonempty bitstrings of length 4 or less which contain the same number of 0s as 1si Thus LEQA 01 10 0011 0101 0110 1001 1010 1100 What does a nitestate machine need to remember about its input to handle this language We could make it remember exactly what the input was up to length 4 This results in a nitestate machine with the structure of a binary tree of depth 4 See Figure 214 Such a binary tree structure corresponds to a table lookup77 in a more conventional language It works for any nite language The preceding example proves Theorem 10 Every nite language is accepted by a nitestate machine The nitestate machine of Figure 24 is not as small as it could be For example if we merged the states H P Q and FF ijust draw a line surrounding them and regard the enclosed area as a new single state 7 we would have reduced the size of this machine by three states without changing the language it accepts Why was this merger possible Because from any of these four states only rejecting states can be reached Being in any one of these four states no matter what the rest of the input the outcome of the computation is always the same viz rejecting the input string A third example Minimizing Finit eState Machines 34 CHAPTER 2 FINITE STATE MACHINES void main void if matcho cout ltlt quotYesquot else cout ltlt quotNoquot 339 boolean match void char first next last first last next getcharo while next EOF last next next getcharo 339 return first last ampamp first EOF 339 Figure 23 Another finitestate program match Can J and K be merged No because a subsequent input 1 leads to an accepting state from J but a rejecting state from Ki What about A and D They both have only rejecting states as their immedi ate successorsi This is not a sufficient reason to allow a merger though What if the subsequent input is 01 Out of A the string 01 drives the machine into state E 7 a fact usually Written as 6A 01 E 7 and out of D the string 01 drives the machine into state 6D01 One of E and Q is rejecting the other accepting This prevents us from merging A and Di en is a merger of two states p and q feasible When it is true that for all input strings s the two states 6ps and 6qs are either both accepting or both rejecting Note that s could be the empty string Which prevents a merger of an accepting With a rejecting state This condition can be rephrased to talk about When a merger is not feasible viz there is an input string s such that of the two states 6ps and 6qs one is rejecting and one is accepting Let7s call such a string s a reason Why p and 4 cannot be merged77 For example the string 011 is a reason Why states B and C in Figure 24 cannot be merged The shortest reasons for this are the strings 0 and 1 A reason Why states D and E cannot be merged is the string 11 The shortest reason for this is the empty string Figure 25 is an illustration for the following observation Which is the basis for an algorithm for finding all the states that can be merged Observation 3 If c is a character and s a string and cs is a shortest reason why p and 4 cannot be merged then s is a shortest reason why 6p c and 64 c 21 STATE TRANSITION DIAGRAMS 35 Figure 24 A nitestate machine for LEQ4 36 CHAPTER 2 FINITE STATE MACHINES Figure 25 Illustrating Observation 3 cannot be merged Observation 3 implies that the algorithm is Figure 26 is correct When carrying out this algorithms by hand it is convenient to keep track of clusters of states 2 Two states p and q are in the same cluster if pq E MergablePairsi As we nd reasons for not merging states ie as we nd the condition of the ifstatement to be true we break up the clusters If p and q are two states that cannot be merged and the shortest reason for that is a string of length k gt 0 then p and 4 will remain together through the rst k 7 1 passes through the repeatloop and get separated in the 16 pass For example consider the nitestate machine in Figure 27 It accepts identi ers with one subscript77 such as A 2 TEMP I LINE1W3 X0341001i Figure 28 shows how the clusters of states develop during execution of the minimization algorithmi States a and I get separated in the third pass which is consistent with the fact that the shortest strings that are reasons not to merge a and b are of length 3 for example 0 77 Other examples are the nitestate machines in Figures 29 and 24 On the nitestate machine of Figure 29 the algorithm ends after one pass through the loop resulting in the machine shown in Figure 210 The binarytreeshaped machine of Figure 24 takes three passes resulting in the machine shown in Figure 211 2Note This works because the binary relation MergablePairs is always an equivalence relation 21 STATE TRANSITION DIAGRAMS 37 MergablePairs States gtlt States i AcceptingStates gtlt RejectingStates repeat UldMergablePairs MergablePairs for all 1097 6 MergablePairs for all input characters 5 if 6pc6qc g UldMergablePairs MergablePairs MergablePairs 7 p797 until MergablePairs UldMergablePairs Figure 26 An algorithm for nding all rnergable states in a nitestate machine Figure 27 A nitestate machine for accepting identi ers With one subscript 38 CHAPTER 2 FINITE STATE MACHINES Pass Passz aim G G 6 quotquot Figure 28 Minimizing the nitestate machine of Figure 27 21 STATE TRANSITION DIAGRAMS 39 Figure 29 A nitestate machine for Checking parity Figure 210 A minimal nitestate machine for Checking parity 40 CHAPTER 2 FINITE STATE MACHINES HOPQRTWXAACCDDEEFF Figure 211 A minimal nitestate machine for LEQ4 22 THE M YHILL NERODE THEOREM All coins dollar 5 quarter 5 halfdollars nickels Figure 212 Equivalence classes of coins 22 The Myhill Nerode Theorem Equivalence Relations Partitions We start with a brief introduction of equivalence relations and partitions because these are central to the discussion of nitestate machinesi lnformally two objects are equivalent if distinguishing between them is of no interest At the checkout counter of a supermarket when you are getting 25 cents back one quarter looks as good as the next But the difference between a dime and a quarter is of interest The set of all quarters is what mathematicians call an equivalence class The set of all dimes is another such class as is the set of all pennies and so on The set of all coins gets carved up or partitioned into disjoint subsets as illustrated in Figure 212 Each subset is called an equivalence class Collectively they form a partition of the set of all coins every coin belongs to one and only one subseti There are nitely many such subsets in this example 6 to be precise Given a partition there is a unique equivalence relation that goes with it the relation of belonging to the same subseti And given an equivalence relation there is a unique partition that goes with it Draw the graph of the relation It consists of disconnected complete subgraphs whose node sets form the sets of the partition 3Note This is easier to visualize when the set of nodes is nite but works also for in nite Partitions E Equivalence Relations Re nement s Equivalence Relations Among Programs CHAPTER 2 FINITE STATE MACHINES All coins 139 1 quotDquot quarters condition nickels Figure 213 A re nement of a partition Just exactly what distinctions are of interest may vary To someone who is co lecting rare coins one quarter is not always going to look as good as the next but one quarter that was minted in 1891 and has a D on it and is in mint condition looks as good as the next such quarteri Our original equivalence class of all quarters gets subdivided capturing the ner distinctions that are of interest to a coin collector The picture of Figure 21 gets more boundary lines added to it See Figure 213 What differences between program do we normally ignore It depends on what we are interested in doing with the programs If all we want to do is put a printout of their source under the short leg of a wobbly table programs with equally many pages of source code are equivalent A very natural notion of equivalence between programs came up in Chap ter 1 10a 105 A further re nement could take running time into account 10 105 and ta it t77 for time A further re nement could in addition include memory usage IOa 105 and ta tb an 8a Sb s77 for space Both t and s are functions of the input The re nements need not stop here We might insist that the two programs compile to the same object code If all we want to do with the program is run it we won t care about further re nements What else would we want to do with a program but run it We might want to modify it Then two programs one with comments and one without are not going to be equivalent to us even if they are indistinguishable at run time So there is a sequence of half a dozen or so successive re nements of notions of and even uncountably in nite sets 22 THE M YHILL NERODE THEOREM 43 program equivalence each of which is the right one for some circumstances Next we will apply the concept of partitions and equivalence relations to nitestate machines Let PARITY be the set consisting of all binary strings with an even number of A Game 1s For example 10100011 6 PARITY 100 g PARITYi Consider the following game played by Bob and Alice 1 Bob writes down a string 1 without showing it to Alice 2 Alice asks a question Q about the string 1 The question must be such that there are only nitely many different possible answers Eigi What is I is out but What are the last three digits of I is allowed 9 Bob gives a truthful answer AQ and writes down a string y for Alice to see Alice still has not seen g r 1f Alice at this point has suf cient information to know whether or not my 6 PARITY she wins If not she loses Can Alice be sure to win this game For example if her question was What is the last bit of 1quot she might lose the game because an answer 1quot and a subsequent choice of y 1 would not allow her to know if my 6 PARITY since I might have been 1 or 11 What would be a better question Alice asks Is the number of Is in I even She is sure to win Tired of losing Bob suggests they play the same game with a different lan guage MORE OS THAN 1S the set of bitstrings that contain more 0s than 1s Alice asks How many more 0s than 1s does I have Bob points out that the question is against the rules Alice instead asks Dues 1 have more 0s than 1s Bob answers YesC Alice realizes that I could be any one of 0 00 000 0000 i i i and concedes defeat Theorem 11 Alice can t win the MORE OS THAN lsgame Proof W hatever niteanswer question Q Alice asks the answer will be the same for some different strings among the in nite collection 0 00 000 0000 i Let 0i4 and 0j be two strings such that 0 S i lt j and AQ0i AQ 0139 The Bob can write down I 0i or z 0 answer Alicels question and then write y 1139 Since Oili g MORE Os THAN ls and 011139 e MORE OS THAN 1S Alice cannot know whether or not 11139 E MORE OS THAN 1S 7 she loses D What does this game have to do with nitestate machines It provides a complete characterization of the languages that are accepted by nitestate machines 1 i 1 4Note Oi means a string consisting ofi Os The Relation EL The Relation 2Q 44 CHAPTER 2 FINITE STATE MACHINES Theorem 12 Consider Bob and Alice playing their game with a language L5 The following two statements are equivalent 1 Alice can be sure to win 2 L is accepted by some nitestate machine In fact the connection between the game and nitestate machines is even stronger Theorem 13 Consider Bob and Alice playing their game with the language L The following two statements are equivalent 1 There is a question that lets Alice win and that can always be answered with one of h di erent answers 2 There is a nitestate machine with h states that accepts L To see that implies I is the easier of the two parts of the proof Alice draws a picture of a hstate machine for L and asks which state the machine is in after reading It When Bob writes down y Alice runs M to see whether or not it ends up in an accepting state The key to proving that 1 implies is to understand why some questions that Alice might ask will make her win the game while others won t Why was it that in the PARITY game asking whether the last bit of I was a 1 id not ensure a win Because there were two different choices for z 11 l and 12 11 which draw the same answer but for which there exists a string y with 11y E PARITY gt 12y E PARITY In this sense the two strings 11 l and 12 11 were not equivalent77 and Alice s question made her lose because it failed to distinguish between two nonequivalent stringsi Such nonequivalence of two strings is usually written as 11 mm 12 Conversely two strings 11 and 12 are equivalent 11 3mm 12 if for all strings y 11y E PARITY 42gt 12y E PARITY De nition 1 Let L be any language Two strings I and z are equivalent with respect to L 1 EL 1 iffor all strings y my 6 L 42gt y 6 L Consider the question Q that made Alice win the DIVISIBLE BY S game What are the last three digits of z or if I has fewer than three digits what is 19T De nition 2 Let Q be any question about strings Two strings I and z are equivalent with respect to Q I EQ z they draw the same answer ie AMI AQI The relation EQ partitions all strings into disjoint subseti This partition induced by EQ is illustrated in Figure 214 22 THE M YHILL NERODE THEOREM 45 Figure 214 The partition induced by Alicels question The subsets of the partition induced by EQ then become the state of a nitestate machine This is illustrated in Figure 215 The start state is the state containing the empty string States containing strings in the language are accepting statesi There is a transition labeled 1 from the state that contains 0 to the state that contains 01 Generally there is a transition labeled 5 from the state containing s to the state containing sci Could it happen that this construction results in more than one transition with the same label out of one state In this example we got lucky 7 A ice asked a very nice question 7 and this won t happen In general it might though As an example Alice might have asked the question If I is empty say so if z is nonempty but contains only 0s say so otherwise what are the last three digits of z or I has fewer than three digits what is I Kind of messy but better than the original question in the sense that it takes fewer different answers The problem is that the two strings 0 and 00 draw the same answer but 01 and 001 don7ti Figure 216 shows where this causes a problem in the construction of a nitestate machine The resolution is easy We arbitrarily choose one of the con icting transitions and throw away the othersi Why is this safe Because EQ is a re nement of EL and it is safe to ignore distinctions between strings that are equivalent under ELi It seems that the nitestate machine in Figure 215 is not minimali We could The best question run our minimization algorithm on it but let s instead try to work on mini 5Note A language in this theory means a set of strings 46 CHAPTER 2 FINITE STATE MACHINES Figure 215 The nitestate machine constructed from Alice7s question Figure 216 A con ict in the construction of a nitestate machine 22 THE M YHILL NERODE THEOREM 47 mizing77 the question Q from which the machine was constructed Minimizing a question for us means minimizing the number of different answers The reason why this construction worked was that EQ was a re nement of EL This feature of the question Q we need to keep But what is the re nement of EL that has the fewest subsets EL itself So the best question is Which subset of the partition that is induced by EL does I belong tagquot This is easier to phrase in terms not of the subsets but in terms of representative strings from the subsets What s a shortest string y with 1 EL yquot Letls apply this idea to the DIVISIBLE BY S problem There are four equiv alence classes 0 00 000 00001000 A10001001100 10 010110 0010 011010101110 and 1 0111 001 011101111 0001 0011 0101 01111001101011011111 The four answers to our best question are A0 10 and 1 The resulting nite state machine has four states and is minimal Lets take stock of the equivalence relations or partitions that play a role in nitestate machines and the languages accepted by such machines As mentioned already every language ie set of strings L de nes induces an equivalence relation EL between strings 1 EL y g for all strings z 12 E L 42gt yz E 22 Every question Q about strings de nes an equivalence relation EQ between strings 7 def I Q y ltgt AQI AQy And every nitestate machine M de nes an equivalence relation E M be tween strings 23 1 EM y amp 5M807 1 5M807 9 24 so denotes the start state of M Note that the number of states of M is the number of subsets into which EM partitions the set of all strings As mentioned earlier for Alice to win the game her question Q must distinguish between strings I and y for which there exists a string 2 with 12 E L gt yz E L In other words she must make sure that 96 L 9 v 1 Q y 25 ie EQ must be a re nement of EL If we regard binary relations as sets of pairs then 25 can be written as 179 EL Iyy 3Q or for the notationally daring 26 The Relations EL 2Q EM 48 CHAPTER 2 FINITE STATE MACHINES Figure 217 Illustrating the uniqueness of a minimal machine EQ g EL 27 Instead of talking about Alice and her question we can talk about a nite state machine and its states6 For the machine M to accept all strings in L and reject all strings that are not in L 7 a state of affairs usually written as LM L 7 M must distinguish between strings I and y for which there exists a strings 2 with 12 E L gt yz E L In other words 1 L 9 1 M 9 28 ie EM must be a re nement of ELi Again if we regard binary relations as sets of pairs then 28 can be written as E M g EL 29 Every machine M with LM L must satisfy 29 a smallest machine M0 will satisfy EMU EL 2 10 Uniqueness How much freedom do we have in constructing a smallest machine for L given analogy becomes clear if you think of a niteestate machine as asking at every step v 7 6 the question What state does the input read so far put me m97 22 THE M YHILL NERODE THEOREM 49 that we have to observe 210 None of any substance The number of states is given of course Sure we can choose arbitrary names for the states But 210 says that the states have to partition the inputs in exactly one way Each state must correspond to one set from that partitioni Figure 21 illustrates this for the language DIVISIBLE BY Si This then determines all the transitions it determines which states are accepting which are rejecting and which is the start state Thus other than choosing different names for the states and laying out the picture differently on the page there is no choice This is expressed in the following theoremi Theorem 14 All minimal nitestate machines for the same language L are isomorphic Unlike our earlier construction ofa nitestate machine from a nonminimal winning question of Alice7s this construction will never result in two transitions with the same label from the same state If that were to happen it would mean that there are two strings I and y and a character c with 1 EL y and dc L yci Since zc L yc there is a string s with zcs E L gt ycs E L and therefore a string 2 cs with 12 E L gt yz E L contradicting 1 EL yo Figure 217 could have been obtained from Figure 214 by erasing those lines that are induced by EQ but not by ELi This is what our minimization algorithm would have done when run on the machine of Figure 215 Summarizing we have the following theoremi Theorem 15 MyhillNerode Let L be a language Then the following two statements are equivalent 1 EL partitions all strings into nitely many classes 2 L is accepted by a nitestate machine Furthermore every minimal nitestate machine for L is isomorphic to the machine constructed as follows The states are the subsets of the partition in duced by EL The start state is the set that contains A A state A is accepting if A Q L There is a transition from state A to state B labeled c if and only if there is a string 1 with z E A and dc E Regular Expressions Kleene7s Theorem The above MyhillNerode Theorem provides a complete characterization of properties that can be determined with nitestate machinesi A totally dif ferent characterization is based on regular expressions77 which you may know as search patterns in text editors Regular languages and expressions are de ned inductively as follows De nition 3 Regular languages 1 The empty set 0 is regular 2 Any set containing one character is regular 50 CHAPTER 2 FINITE STATE MACHINES 5 If A and B are regular then so are A U B AB and Aquot The union concatenation and Kleene star operations are de ned as usual AUBzzzerrzEB ABzyz Aandy B AzlzgzkhZOandziEAforalli l Observation 4 Finite languages are regular De nition 4 Regular expressions 1 The symbol D is a regular expres sion and L ll 2 Any single character c is a regular expression and Lc 5 If a and B are regular expressions then so are a U B 15 and ozquot and W W Lltagt we L016 Maw and Lltagt ltLltagtgt Observation 5 A language L is regular and only if there is a regular expres sion E with L The important result in this section is the following Theorem 16 Kleene s Theorem The following two statements are equiv alent 1 L is regular 2 L is accepted by some nitestate machine Proof Both parts of this proof are inductive constructionsl To construct regular expressions from nitestate machines we number the states and carry out an inductive construction with the induction being over this numbering of the states This is a nontrivial example of a proof by induction and a nice illustration of the fact that inductive proofs often become easier once you decide to prove a stronger result than you really wante i To construct nitestate machines from regular expressions we do an duction over the structure77 of the expression This is a nice example of the fact that induction while strictly speaking a technique that is tied to natural numbers can be thought of as extending to other sets as well Here are the details 2 1 To construct a regular expression from a given nitestate machine M rst number the states of the machine 1 H l q with state 1 being the start 44in 22 THE M YHILL NERODE THEOREM 51 Figure 2118 Illustrating the notion of a string making a machine pass throug states state De ne L2 to be the set of all strings which make the machine go from state i into state j without ever passing through any state numbered higher than kl For example if the machine of Figure 2118 happens to be in state 1 then the string 12a will make it rst go to state 2 and then to state 3 In this sequence 1 A 2 A 3 we say that the machine went through state 2 It did not go through states 1 or 3 which are only the starting point and the endpoint in the sequencer Since it did not go through any state numbered higher than 2 we have 12a 6 Lgfgi Other examples are babb E L 2 and a E ng in fact a ngi In this example the language accepted by the machine is LE In general the language accepted by a nitestate machine M is LM ULgf 211 f where the union is taken over all accepting states of M1 What s left to show is that these languages L are always regulari This we show by induction on kl For k 0 ng is nite It contains those characters that label a transition from state i to state ji lfi j the empty string gets added to the set For k gt 0 L3 L 1L gl L if U L2 212 This equation amounts to saying that there can be two ways to get from state i to state j without going through states numbered higher than kl Either we go through 16 or we don7t corresponding to the subexpression before the union and the subexpression after the union Figure 2119 illustrates this Figure 2120 shows some of the steps in the construction of a regular expression from the nitestate machine of Figure 2118 We simplify the subexpressions as we go Expression describes language Lg LEl j Lil Some parentheses are omitted A is short for 0quot hence L A by the de nition of the operation We wouldnlt want to miss a chance to be obscure would we 52 CHAPTER 2 FINITE STATE MACHINES Figure 219 The pattern of induction for constructing the regular expressions L2 in Kleenels Theorem 1 To construct nitestate machines from regular expressions we use what is called induction on the structure of the expression77 or structural inductioni77 This means that nitestate machines are rst constructed for small subexpressions then combined to form machines for larger subexpressions and ultimately for the whole expression For example if we want to convert the expression E abb U baaquotbab a machine Maa for the subexpression aaquot is shown in gure 221 For simplicity let s adopt the convention that if a transition goes to a reject ing state from which the machine cannot escape anymore then we won t draw the transition nor that dead77 state This simpli es the picture for Mum see Figure 222 A machine M5 is easier yet see Figure 223 We can combine M5 and Maa to get M50111 shown in Figure 224 Adding parts that correspond to subexpressions ab and bab completes the construction see Figure 225 This seems easy enough but what if the expression had been just slightly different with an extra 12 in front E babb U baaquotbab Then our construction would have gotten us this machine ME in Figure 226 This machine ME has a aw there are two transitions labeled 1 out of the start state When we run such a machine what will it do What should it do presented with such an ambiguity Can we de ne the semantics ie can we de ne how such a machine is to run in such a way that the machine ME accepts the very same strings that the expression E describes 22 THE M YHILL NERODE THEOREM E A U a E2 b E3 E31 2 E32 A U b E33 E31 1 E32 a Egg E111 ai E112 a E113 E211 2 E212 A U b E213 E311 ba E312 7 ba z U a E313 Era E12ltE212gtE3gt u E113 abba u a whim Efl 7 a EfQ 7 a fr Efg E221 0 E222 5 E33 E31 ba E32 ba E33 E31 E 3E 3E 1 u Efl abbabab u ababa u m aquotbbquota Va ba z U abquota Figure 220 Converting the nitestate machine from Figure 218 into a regular expression 54 CHAPTER 2 FINITE STATE MACHINES Figure 221 The machine Maa Figure 222 The machine MOZW7 a simpli ed drawing ZO gt Figure 223 The machine Mb Figure 224 The machine Muddy 22 THE M YHILL NERODE THEOREM 55 O xO RQ Figure 225 The machine ME y 1 a b 0 9 quot 9 36 Figure 226 The machine ME 56 CHAPTER 2 FINITE STATE MACHINES Figure 227 The machine MEN After reading an initial 127 should ME be in state 2 or in state 7 We want to accept both babb and baababi Being in state 7 after the rst I give us a chance to accept babb and being in state 2 gives us a chance to accept baababi This suggests that the right way to run this machine is to have it be in both states 2 and 7 after reading the rst bi With this way of running the machine7 which states would it be in after reading an a as the second character In states 3 and 8 After reading a b as the third character7 it can only be in state 9 7 After reading another I 7 for a total input string of babb 7 M3 is in state 10 and accepts the input There is one more issue that this example does not address What if some such machine ends up in a set of states some of which are accepting and some are rejecting The expression E 1212a U baaquotbab provides an example Our construction will result in the machine MEN of Fig ure 227 After reading bba7 the machine is in state 57 which is rejecting7 and in state 97 which is accepting Since bba is a string described by E 7 it should be accepted by MEh That settles the issue a st7ing is accepted if at least one of the states it puts the machine in is an accepting state Our conventions about running these machines and knowing when a string is accepted are the semantics of nondeterministic nitestate machines77 These 7This could be up to some discussion depending on how we View our convention of not drawing a dead state ie a rejecting state from which the machine cannot escape If we take the View that the state is there i we just don7t draw it i then at this point we should say that the machine would be in state 9 and that invisible state say 1139 This is clumsy It is more elegant 7 although ultimately of no important consequence i to say that the machine is only in state 939 22 THE M YHILL NERODE THEOREM 57 Figure 228 Converting ME into a deterministic machine conventions can be applied to more powerful programs as well and we will do so in a later chapter on computational complexity where the concept of nonde terminism will play a crucial role in de ning a class of computational problemsi Nondeterministic C77 for example could be C with the extra feature of a non deterministic branch nondetbranch x 0 x 1 The way to think about the execution of such nondeterministic programs is that there is more than one path of execution Tracing the execution results in a tree and a program is said to accept its input if at least one of the paths leads to acceptance Can we convert this new kind of machine into a standard deterministic nitestate machine This task amounts to a search of the execution tree77 which we do in a breadth rst approachi Figure 228 gives an example convert ing the machine ME into a deterministic one The states of the deterministic machine are the sets of states of MEL Many of these sets of states may not be reachable from the start state and can be discarded In the deterministic machine the state reached from a state A via a transition 5 6Ac is the set of those states I of ME to which there is a c transition in My from some state a 6 Al The algorithm for constructing a nondeterministic machine from a regular expression is easier to describe if we allow yet another form of nondetermin istic behavior making a spontaneous transition ie a transition that does not consume an input character The standard term is a A transitioni The inductive algorithm for constructing a nondeterministic nitestate machine ME from an arbitrary regular expression E then works as shown in Figure 229 An example that uses all the parts of this algorithm is the machine shown in Figure 230 58 CHAPTER 2 FINITE STATE MACHINES 1 M9 is the following machine 2 For any single character 0 MC is the following machine LVC gt gt O 3 If a and B are regular expressions then Maug M043 and MM are constructed from Ma and M5 as shown below Constructing Mm from Ma Figure 229 An algorithm for converting regular expressions to nitestate Ina chines 22 THE M YHILL NERODE THEOREM 59 1 O gtO gtO gtO gtO gtO gt Figure 230 The machine Maamabbx Figure 231 A deterministic version of Maamabbx Nondeterministic machine With A transitions can be turned into determin istic ones With the same setof states approach used earlieri For example the machine in Figure 230 turns into the machine in Figure 231 This concludes the proof of Kleene7s Theoremi D Given that nitestate machines and regular expressions are equivalent concepts FiniteState Machines or we can choose to approach some problem in terms of one or the other Some Regular Expressions questions are easier to deal With in terms of nitestate machines others in terms of regular expressions Here are some examples all of them variations of the question of Which languages are regular Question 1 Is the set of binary numbers that are divisible by 2 regular 60 CHAPTER 2 FINITE STATE MACHINES 0 Figure 232 A piece of a nitestate machine This is easy in either domain The right regular expression is 0 U 1quot0 Question 2 Is the set of binary numbers that are divisible by 3 regular The answer is yes but it seems nearly impossible to build a suitable regular expression After all what is the common pattern of 11 110 10000000010 1001 Yet it is not all that hard to build a nitestate machine for this language with the right approach anyway The MyhillNerode Theorem tells us that we would have to gure out exactly what it is that we want to keep track of as the input gets processed we know that the input so far was a number that was divisible by 3 then we know that after reading one more 0 the number is again divisible by 3 This is so because reading that 0 amounted to multiplying the previous number by 2 What if a 1 had been read instead This would have amounted to multiplying the previous number by 2 and adding 1 The resulting number when divided by 3 would yield a remainder of 1 This translates into a piece of a nitestate machine shown in Figure 232 The complete machine is shown in Figure 233 The four equivalence classes of EL and hence the states of the minimal machine for L are A and the three sets of binary numbers which when divided by three yield a remainder of 0 1 and 2 These remainders are used as the labels of the three states Question 3 Are regular languages closed under union 1e if A and B are regular is their union A U B regular as well The answer is yes It follows from the de nition of regular sets and expres sions In terms of nitestate machines this requires an argument involving nondeterministic machine as used in the proof of Kleenels Theorem Question 4 AIE regular languages closed under complement 1e if A is regular is A z z z A regular as well This is most easily dealt with in terms of nitestate machines If M is a nitestate machine for A then a nitestate machine for A can be obtained by turning accepting states into rejecting ones and vice versa There is no equally simple argument in terms of regular expressions 22 THE M YHILL NERODE THEOREM 61 Figure 233 A nitestate machine for binary numbers divisible by 3 Question 5 Are regular languages closed under set difference liei if A and B are regular is their difference A 7 B z z z E A and z B regular as well There is a construction based on nitestate machine that proves this closure result and is interesting in its own rig ti Question 6 Is the set of syntactically correct C programs regular It is not and the only proof method presented so far is to argue that there are in nitely many equivalence classes induced by ED Here is an in nite list of nonequivalent strings main int main int main int main int This shows that parsing programs which is a necessary part of compiling them cannot be done with an amount of memory that does not depend on the input that is being parsedi As we will see in the next chapter it takes a stack to parse 62 CHAPTER 2 FINITE STATE MACHINES 23 Programs That Process FiniteState Machines Unlike the set of all programs which as shown in Chapter 1 resist all attempts at predicting their lO behavior nitestate machines are much more wellbehaved This comes at a price They are much less powerful Figure 234 illustrates how two nitestate machines can be combined into one which does the work of both This provides an easy proof of some closure properties The choice of accepting states shown in Figure 234 illustrates a proof of closure under set difference Different choices would prove closure under various binary operations on sets 24 The Pumping Lemma for Regular Languages Pumping is a second technique to prove nonregularityi It is interesting in its own right although no more powerful than the analysis of EL that we have discussed already in Sections 77 Pumping is important if for no other reason then because unlike the analysis of EL in Myhill Nerode pumping arguments also work for the more powerful programs we will consider in the next chapter Lemma 3 Pumping Lemma for Regular Languages If L is a regular language then there is a constant k such that for every string w in L of length h or more the following is true There are three strings u v I such that 1 w uvz and 2 for all i 2 0 uviz E L and 5 lvl gt 0 Let7s use this Lemma to prove that the language L anbn n 2 l is not regular Assuming it was Then the Lemma applies Let h be the constant said to exist in the Lemmai Consider the string w akbki The length of w is h or more in fact 2h hence statements 1 7 3 from the Lemma apply implying that it is possible to split w into three parts w uvz such that lvl gt 0 and uv21 6 Li But this is not true No matter what threeway split of w one tries uv21 is never of the form of equal numbers of as and bls One can come up with a more detailed argument for this The challenge is to cover all ways in which the strings could get divided up into three pieces An added challenge is to come up with a concise argumenti Here is an attempt The substring 1 cannot contain more than one type of character because otherwise v2 contains characters in an order not permitted in L Hence at most one type of character take part in the pumping from uvz to uv2z which therefore does not contain equal numbers of both characters anymore This contradiction shows that L is not regular El 24 THE PUMPING LEMMA FOR REGULAR LANGUAGES Figure 2342 Combining two nitestate machines into one 63 CHAPTER 2 FINITE STATE MACHINES Why is this so messy The Pumping Lemma can be stated as follows L regular gt There is a constant k such that for all strings w E L with 2 Is there are strings u v z with w uvz and lvl gt 0 such that for all i 2 0 uviz E L The above statement is of the form L regular B77 where B is that complicated statement with four alternating quanti ersl Since we are trying to prove that some languages are not regular a more useful version of the statement is L not regular 5 Bl Spelled out in detail this version reads L not regular 4 For all constants Is there is a string w E L with 2 k such that for all strings u v z with w uvz and lvl gt 0 there is an i 2 0 with uviz g L Thus we can prove that some language L is not regular by proving the above fourline statement B For all g L h This is what we did in the previous example Here is another one Another Example Lets take the language that consists of strings like 12341111345 100001000020000 10203045051020809 111112222233333 The language consists of strings of the form a B 7 that represent a correct equation between decimal integersl This language L is not regular a fact we prove by proving the statement B above How do we prove something for all constants k By starting out the proof by saying Let h be an arbitrary constant77 and carrying the h along as a parameter of the argument What s next We need to show that there exists a string w with certain properties To show this all we need to do is exhibit one such stringl In this example let s pick w to be the string 24 THE PUMPING LEMMA FOR REGULAR LANGUAGES 65 Note how the k plays its role Whats the next step We have to show that for all strings u7 v I which represent a threeway breakup of w w uvz and which don7t have the second piece empty lvl gt 077 7 there is a constant 239 with uviz g L This is the hard part of the proof because we somehow have to provide an argument that covers all possible such threeway breakups of w It can be done7 by dealing with an exhaustive set of cases Here is such an exhaustive set of cases for this example Case 1 1 contains the Then uvoz g L if for no other reason then because it does not have an in it Case 2 1 does not contain the Then 1 lies entirely on one side of the and pumping with any i f 1 changes that side of the equation but not the other7 thus creating a string outside of L Exercises Ex 21 Draw the smallest nitestate machine M for the language of all bitstrings that contain the substring 011 Ex 22 Draw the smallest nitestate machine M for the language of all bitstrings that contain the substring 011 Make sure you provide a 0 and a 1 transition out of every state Ex 23 Carry out the minimization algorithm of Figure 26 for the nite state machine shown below Show the development of the clusters of states just like Figure 28 did Ex 24 Draw a nitestate machine on which the minimization algorithm runs through more than 10 passes Ex 25 Let L be the language of all bitstrings that contain a run of three consecutive 0s Is it true that 01 EL 001 Explain Ex 26 H H L is the language of all bitstrings that start with a 1 and end with a 07 then 01 EL 00 to H L is the language of all bitstrings of length 87 then 0001 EL 0011 9 Let L be the language of all bitstrings I such that 1 contains at least one 0 For example7 01 6 L7 1111 g L How many equivalence classes does EL induce Minimizing nit est ate machines The MyhillNerode Theorem 66 CHAPTER 2 FINITE STATE MACHINES 4 Let L be the language of all bitstrings I such that 1 contains at least one 0 and at least one 1 For example7 01 6 L7 1111 g L7 00 g L How many equivalence classes does EL induce Ex 27 Let L be the language of binary strings whose third bit from the end is a 1 Give one string from each of the equivalence classes induced by EL Ex 28 Same for the language of bitstrings whose rst two bits are equal to its last two bits Ex 29 Give one representative of each equivalence class of EL for L z z 1 contains the substrihg 000 Ex 210 Consider the following language L over the alphabet E ab L zy Ly E al4r and I does not start with the same letter as y For every equivalence class of EL give one shortest string from the class Ex 211 Is it true that 1 EL y implies 12 EL yz Is it true that 12 EL yz implies 1 EL y When your answer is no7 give a counterexample Ex 212 Are the two relations EL and EE thatls L7 the complement of L always the same7 for any given L Either argue that they are7 or show an example were they aren t Ex 213 7 Do the partitions that go with EL and with ELTEU thatls Lm zm z E L always have the same equivalence classes Either argue that they always do7 or show an example were they don7t 175 is 1 written b ackwards Ex 214 Which of the following languages is regular Just circle Yes or No for each language Do not give explanations 1 The language described by abaquotbquot U aabquot 2 Strings containing the word while 3 Strings containing two opening parentheses with no closing parenthesis in between the two7 eg abc de f77 4 Strings containing more opening parentheses than closing ones7 eg 0 77 5 Strings containing all their opening parentheses before all their closing ones7 eg Xy77 24 THE PUMPING LEMMA FOR REGULAR LANGUAGES 67 6 Strings of even length whose rst half and second half both start with the same letter7 eg abcabaeeee Ex 215 Consider two nitestate machines that accept languages A and B and consider their crossproduct machine As discussed in class7 one can always choose the accepting states of the crossproduct machine such that it accepts A O B Can one always choose the accepting states of the crossproduct machine such that it accepts 1 A U B 7 2 A7B7 That s IzzEAandz 3 AB 7 That s A concatenated with B my z E A and y E 4 Strings in A U B of length ve or more7 5 A 7 Ex 216 Derive an asymptotic bound on the length of the expression con structed from a nitestate machine in the proof of Kleene7s Theorem Assume we are dealing with bitstrings only Ex 217 Consider the problem of taking an arbitrary nondeterministic nitestate machine that accepts some language A and modifying the machine to accept the complement of A instead ie7 all the strings that are not in A Does the following approach work Make all rejecting states of the nonde terministic machine into accepting states and all accepting states into rejecting states7 Brie y explain your answer Ex 218 For any k 2 0 let Lk be the language of bitstrings whose rst k bits equal their last k bits How many states does a deterministic nitestate machine for Lg need7 Same for a nondeterministic machine How long is a regular expression for L167 Ex 219 Give three properties that are decidable for nitestate machines but undecidable for arbitrary programs Ex 220 Which of the languages in Figure 7 are regular7 Ex 221 Consider creating the crossproduct machine of two given ma Regular Expressions Nondeterminist ic Machines CrossProduct Construction Miscellaneous 68 CHAPTER 2 FINITE STATE MACHINES chines and choosing the accepting states such that the new machine accepts the intersection of the languages of the two old machines 1 Give an example where the crossproduct machine is minimal b If the crossproduct machine is minimal7 does that imply that the two factors in the product had to be minimal Give an argument or a counterex ample Ex 222 For any program p de ne Lp to be the set of input strings on which the program prints the word Yes and terminates ls it decidable whether or not a program p has a regular language L1 Brie y justify your answer Ex 223 Let FSM EQUIVALENCE be the problem of deciding7 given two nite state machines P and Q7 whether or not LP Let FSM EMPTINESS be the problem of deciding7 given a nitestate machine M7 whether or not LM 0 Describe how a crossproduct construction can be used to transform FSM EQUIVALENCE into FSM EMPTINESS Ex 224 Construct a nitestate machine for the language I z z E 07 lquot and z 000001quot First construct a nondeterministic machine that is as small as possible7 then apply the subset construction7 then minimization Ex 225 For two of the nonregular languages in Figure 7 use the pumping lemma to prove that they are not regular Ex 226 Prove that every in nite regular language contains a string whose length is not a prime number Ex 227 Prove that the set of strings that are nite pre xes of this in nite s ring 0 llOlllOOlOlllO llllOOOlOOllOlOlOll is not regular Ex 228 Formulate a stronger version of the pumping lemma7 one that says not only that pumping occurs somewhere in a long enough string but that it occurs within every long enough substring Use this stronger version to prove two languages from 3 Figure 7 not regular which cannot be proven not regular with the original weaker version 8To do This is not in the sample solutions yet Chapter 3 ContextFree Languages 31 ContextFree Grammars As we saw at the end of the previous chapter7 one feature of programming languages that makes them nonregular is the arbitrary nesting of parenthesis in expressions Regular expressions cannot be used to de ne what syntactically correct expressions look like Contextfree grammars77 cani An example of a contextfree grammar is this E7EE E7EgtltE EHUE E71 E7y The way this grammar 7 call it G1 7 is used is to start with the symbol on left of the arrow in the rst line7 El This is the start symbol77 7 the string of length 1 we start out with We then grow that string by repeatedly replacing what s on the lefthand side of an arrow with what s on the righthand side The best way to keep track is a tree 70 CHAPTER 3 CONTEXT FREE LANGUAGES E E x E I E E There are choices of which replacements to make The choices made above resulted in a tree whose leaves read from left to right read I y X I 9 The grammar G1 is said to derive that string 1 y X z y E LG1i The tree is a derivation tree for the string Derivation trees are also called parse trees They are used in compilers to know how to translate a given expression or a whole program into machine language and in interpreters to know how to evaluate an expression or interpret a whole programi Our sample grammar does not serve that purpose well though This is because it allows a second derivation tree for the same string E E E E E E E E x y X x V Such a grammar is said to be ambiguousi The two parse trees for the string 1 y X I y lead to two different evaluations of the expression If we plug in z 1 and y 5 the rst tree leads to a value of 36 for the expression whereas the second one leads to a value of 31 Of the two trees only the rst one matches our conventions about the precedence of arithmetic operations The rst one is right the second one is wrong The problem is this grammar G1 while it does perfectly well describe the language in question does not help us de ne the one and only correct way to parse each string in the language The following 32 PARSING 71 grammar G2 does do that ET T TgtltF F E I y seesaw lllllll F This grammar only allows one derivation tree the right one for any arithmetic expressions involving X parentheses and the variables I and y The tree for the expression 1 y X I y is T E x m s m e m s 32 Parsing RecursiveDescent Parsing A grammar like G2 above is easily turned into a parser ie a program that determines Whether or not a given input string is in the language and does so necessarily by building a parse tree implicitly or explicitly See Figure Bill The program is nondeterministic though 7 certainly a aw we do not want to tolerate for very long In What sense does this program parse expressions CHAPTER3CONTEXDFREELANGUAGES main E0 if getchar EOF ACCEPT else REJECT E nondetbranch E terminal 77 TO T T nondetbranch T terminal F0 F F nondetbranch terminal E terminal terminal x terminal y terminal char 6 if getchar c REJECT Figure 31 A nondeterministic recursivedescent parser 32 PARSING 73 Being a nondeterministic program the program as a whole is said to accept an input string if there is at least one path of execution that accepts it Consider again the string zy gtlt The one path of execution that results in accep tance is the one where the rst execution of E in turn calls E termina1 and Ti These calls correspond to the children of the root of the derivation tree If we chart the calling pattern of the accepting execution we end up drawing the parse tree The accepting computation looks like a preorder traversal 0f the parse tree of the input string The above construction shows how to turn any contextfree grammar into a program that is like the nite programs of Chapter 2 except that it uses two additional features recursion and nondeterminismi Such programs are often called pushdown machines77 or pushdown automata pda si77 They are equivalent to nitestate machines augmented by a stack to implement recursioni Thus the above example generalizes to the following theoremi Theorem 17 For every contextfree grammar G there is a pushdown machine M with LM LG The converse is also true providing a complete characterization of contextfree languages in terms of a type of programi Theorem 18 For every pushdown machine M there is a contextfree grammar G with LM LG We don7t prove this here Deterministic Parsing Intrinsically Nondeterministic ContextFree Languages With regular languages and nitestate machines it was always possible to re move the nondeterminism from the machines The trick was to replace states by sets of states This worked because the power set set of subsets of a nite set was again a nite set This approach does not work for pushdown machines because a set of stacks or even just two stacks cannot be implemented with a single stacki Without giving any proof of this here is an example of a grammar that derives an intrinsically nondeterministic language The language is very simple all bitstrings of odd length whose middle character is a ll SHBSBll BHOll To parse this language with a pushdown machine nondeterminism is needed We do not prove this here but the intuition is that the parser must keep building up a stack of recursive calls for the rst half of the input string and climb out of the recursion during the second half The problem is with information limited by a constant amount it is not possible to know when the second half startsi Chomsky Normal Form 74 CHAPTER 3 CON TEXT FREE LANGUAGES A Predictive RecursiveDescent Parser The example is after Aho and Ullman Pn39ncz39ples 0f Compiler Design 1978 pl176ffl While a deterministic recursivedescent parser does not exist for all context free languages some languages are simple enough to yield to such an approach For example the grammar for arithmetic expressions used earlier can be trans formed without changing the language into the following E A TE E A TE l A T A FT T A XFT l A F A E F A I F A y The work done by the rst two intermediate strings of the form productions version which was to generate TTT is done by the rst two productions of the new version The new grammar leads to a parser in which the decision which of the nondeterministic paths has a chance of leading to acceptance of the input can be made on the basis of looking at the next character of the input This is so because whenever the grammar has several righthand sides for the same lefthand symbol the right hand sides differ in their rst character The resulting deterministic parser in shown in Figure 32 A General Parsing Algorithm Instead of using nondeterminism which is impractical even when implemented by a deterministic treetraversal one can use a dynamic programming77 ap proach to parse any contextfree languagei Dynamic programming is a type of algorithm somewhat resembling divideandconquer which inductively or recursively depending on the implementation builds up information about sub problems It typically has 0n3 time complexity There are two steps to using this technique First we change the grammar into Chomsky Normal Form77 then we apply the actual dynamic programming algorithml Every contextfree grammar can be converted into an equivalent one in which each production is of one of the two forms 32 IZAIlEUTV 75 main E if getchar EOF AC else REJECT E T E E f if NEXTCHAR 77 terminal T E else do nothing just return T F T T f if NEXTCHAR 77 terminal F T else do nothing just return F switch NEXTCHAR case 77 terminal E terminal break case 7x terminal x break case y terminal y bre default REJECT Figure 32 A deterministic recursivedescent parser 76 CHAPTER 3 CON TEXT FREE LANGUAGES AHBC A A a where A B C are syntactic variables not necessarily different ones and a is a terminal symbol This form of a contextfree grammar is called Chomsky Normal Formi77 To see how this conversion can be done consider this production A A BCdEfG 31 The production 31 can equivalently be replaced by the set of productions A A BCDEFG 32 D A d F A f and the production 32 can then be replaced by the set of productions A A BC 0 A CD D A DE E A EF F A FG The example below is from Hopcroft and Ullman Introduction to Automata Theory Languages and Computation 1979 pp 1401 CYK Parsing An Figure 33 shows an example The length 2 starting position 5 7 eld Example of Dynamic contains all those variables of the grammar from which one can derive the sub Programming string of length 2 that starts at position 3 The string is ab The variables are S and Or The rows of the table get lled in from top length1 to bottom length5i The whole string is in the language if the start symbol of the gram mar shows up in the bottom eldi Filling in a eld makes use of the contents of elds lled in earlier in a pattern indicated by the two arrows in the Figure The algorithm is easily modi ed to yield a parse tree or even sets of parse treesi 33 The Pumping Lemma for ContextFree Gram mars The grammar 33 THE PUMPING LEMMA FOR CONTEXT FREE GRAMMARS 77 S A AB B0 A A BA a B H CO b C A AB a b a a b a stamng position gt 1 2 3 4 5 lmgth 1 2 Figure 33 An example of CYK parsing 78 CHAPTER 3 CON TEXT FREE LANGUAGES S A 0 S 1 0 1 generates the language L4 0n1nn2 1 0 means a string of n Osi Similar grammars generate L5 0 1nom1mnm 21 L5 anbmcnm n 2 1 L7 anbmcmdnnm 2 1 If we think of 0 a and b as opening parentheses and 1 c and d as closing parentheses then these language all are examples of balanced parenthesesi1 More complicated languages arise if we try to have equal numbers of not just two but three or more different characters as for example in L3 uniLC n 21 and if we match numbers of characters beyond a nesting pattern as for example in L9 anbmcndm nm 21 If you try to write contextfree grammars for L3 and L9 you sooner or later get frustrated trying to achieve the speci ed equalities between the exponents ie the numbers of repetitions of characters in the de nitions of these lan guagesi In fact Theorem 19 L3 and L9 are not contextfree The languages L3 and L9 are of no practical interest But after we develop a proof technique for showing that these languages are not contextfree we will be able to use that technique to show that some aspects of programming languages are not contextfree either The proof of Theorem 19 uses a cuttingandpasting argument on the parse trees of contextfree grammarsi It is the most common argument for proving languages not to be contextfreer The heart of the argument is that every contextfree language has a certain closure property The fact that certain strings are in the language forces other strings to be in the language as well A 1L7 is an example of nesting of different types of parentheses Replace a and d by opening and closing parentheses and b and c by opening and closing square brackets Then L7 becomes quotlmlmquotlmm Z 1139 3 be THE PUMPING LEMMA FOR CONTEXT FREE GRAMMARS 79 gt log bn height repetition I I I I I lt gt 11 leaves gt Figure 34 Illustrating the proof of Theorem 19 language that does not have the closure property cannot be contextfreer The details of that closure property are developed next If a language L is contextfree there is by de nition a contextfree grammar G that generates L L LGi Let b be the maximum length of righthand sides of productions of G In other words I is a bound on the maximum number of children for nodes in parse trees of G Then a parse tree with n leaves must be of height at least log n where height is de ned to be 0 for a tree consisting of a single node This means that a tree with n leaves must have a path from the root to a leaf with at least logbn 7 1 interior nodesi What if n is so large that log n 7 1 exceeds the number of different lefthand sides of productions in C These are also called syntactic variables Then some syntactic variable must show up at least twice along that path Figure 34 illustrates this Pick such a variable call it A and pick two occurrences of A along one path These two occurrences of A split the string w that the tree derives into ve parts labeled u v z y 2 in Figure 34 The substring vzy is derived from the rst of the two occurrences of the variable A the substring z from the second occurrencei Knowing that we can derive z from A the tree shown in the top half of Figure 35 is also a parse tree in this grammari 1t derives the string uzzi There are other trees we can construct For example as illustrated in the bottom half of Figure 35 the second occurrence of A can be made to derive vzy resulting in a tree that derives the string uvvzyyzi No need to stop there We can build trees that derive uvvvzyyyz uvvvvzyyyyz in fact any string uvizyiz for any i 2 2 For i 01 the string uvizyiz becomes uzz and uvzyz respectively This lets us summarize the effect of all this cuttingandpasting of trees as the fol CHAPTER 3 CON TEXT FREE LANGUAGES Figure 35 Deriving uzz and uvvzyyz


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.