Introduction to Theory of Computation PDF

Introduction to Theory of Computation Anil Maheshwari Michiel Smid School of Computer Science Carleton University Ottawa Canada {anil,michiel}@scs.carleton.ca August 29, 2024 ii Contents ...

Introduction to Theory of Computation Anil Maheshwari Michiel Smid School of Computer Science Carleton University Ottawa Canada {anil,michiel}@scs.carleton.ca August 29, 2024 ii Contents Contents Preface vi 1 Introduction 1 1.1 Purpose and motivation..................... 1 1.1.1 Complexity theory.................... 2 1.1.2 Computability theory................... 2 1.1.3 Automata theory..................... 3 1.1.4 This course........................ 3 1.2 Mathematical preliminaries................... 4 1.3 Proof techniques......................... 7 1.3.1 Direct proofs....................... 8 1.3.2 Constructive proofs.................... 9 1.3.3 Nonconstructive proofs.................. 10 1.3.4 Proofs by contradiction.................. 11 1.3.5 The pigeon hole principle................. 12 1.3.6 Proofs by induction.................... 13 1.3.7 More examples of proofs................. 15 Exercises................................. 18 2 Finite Automata and Regular Languages 21 2.1 An example: Controling a toll gate............... 21 2.2 Deterministic finite automata.................. 23 2.2.1 A first example of a finite automaton.......... 26 2.2.2 A second example of a finite automaton........ 28 2.2.3 A third example of a finite automaton......... 29 2.3 Regular operations........................ 31 2.4 Nondeterministic finite automata................ 35 2.4.1 A first example...................... 35 iv Contents 2.4.2 A second example..................... 37 2.4.3 A third example...................... 38 2.4.4 Definition of nondeterministic finite automaton.... 39 2.5 Equivalence of DFAs and NFAs................. 41 2.5.1 An example........................ 44 2.6 Closure under the regular operations.............. 48 2.7 Regular expressions........................ 52 2.8 Equivalence of regular expressions and regular languages... 57 2.8.1 Every regular expression describes a regular language. 58 2.8.2 Converting a DFA to a regular expression....... 61 2.9 The pumping lemma and nonregular languages......... 68 2.9.1 Applications of the pumping lemma........... 70 2.10 Higman’s Theorem........................ 77 2.10.1 Dickson’s Theorem.................... 77 2.10.2 Proof of Higman’s Theorem............... 78 Exercises................................. 81 3 Context-Free Languages 91 3.1 Context-free grammars...................... 91 3.2 Examples of context-free grammars............... 94 3.2.1 Properly nested parentheses............... 94 3.2.2 A context-free grammar for a nonregular language... 95 3.2.3 A context-free grammar for the complement of a non- regular language..................... 97 3.2.4 A context-free grammar that verifies addition..... 98 3.3 Regular languages are context-free................ 100 3.3.1 An example........................ 102 3.4 Chomsky normal form...................... 104 3.4.1 An example........................ 109 3.5 Pushdown automata....................... 112 3.6 Examples of pushdown automata................ 116 3.6.1 Properly nested parentheses............... 116 3.6.2 Strings of the form 0n 1n................. 117 3.6.3 Strings with b in the middle............... 118 3.7 Equivalence of pushdown automata and context-free grammars 120 3.8 The pumping lemma for context-free languages........ 124 3.8.1 Proof of the pumping lemma............... 125 3.8.2 Applications of the pumping lemma........... 128 Contents v Exercises................................. 132 4 Turing Machines and the Church-Turing Thesis 137 4.1 Definition of a Turing machine.................. 137 4.2 Examples of Turing machines.................. 141 4.2.1 Accepting palindromes using one tape......... 141 4.2.2 Accepting palindromes using two tapes......... 142 4.2.3 Accepting an bn cn using one tape............. 143 4.2.4 Accepting an bn cn using tape alphabet {a, b, c, 2}.... 145 4.2.5 Accepting am bn cmn using one tape............ 147 4.3 Multi-tape Turing machines................... 148 4.4 The Church-Turing Thesis.................... 151 Exercises................................. 152 5 Decidable and Undecidable Languages 157 5.1 Decidability............................ 157 5.1.1 The language ADFA.................... 158 5.1.2 The language ANFA.................... 159 5.1.3 The language ACFG.................... 160 5.1.4 The language ATM.................... 161 5.1.5 The Halting Problem................... 163 5.2 Countable sets........................... 164 5.2.1 The Halting Problem revisited.............. 168 5.3 Rice’s Theorem.......................... 170 5.3.1 Proof of Rice’s Theorem................. 171 5.4 Enumerability........................... 173 5.4.1 Hilbert’s problem..................... 174 5.4.2 The language ATM.................... 176 5.5 Where does the term “enumerable” come from?........ 177 5.6 Most languages are not enumerable............... 180 5.6.1 The set of enumerable languages is countable..... 180 5.6.2 The set of all languages is not countable........ 181 5.6.3 There are languages that are not enumerable...... 183 5.7 The relationship between decidable and enumerable languages 184 5.8 A language A such that both A and A are not enumerable.. 186 5.8.1 EQ TM is not enumerable................. 186 5.8.2 EQ TM is not enumerable................. 188 Exercises................................. 189 vi Contents 6 Complexity Theory 197 6.1 The running time of algorithms................. 197 6.2 The complexity class P...................... 199 6.2.1 Some examples...................... 199 6.3 The complexity class NP..................... 202 6.3.1 P is contained in NP................... 208 6.3.2 Deciding NP-languages in exponential time...... 208 6.3.3 Summary......................... 211 6.4 Non-deterministic algorithms.................. 211 6.5 NP-complete languages..................... 213 6.5.1 Two examples of reductions............... 215 6.5.2 Definition of NP-completeness.............. 220 6.5.3 An NP-complete domino game............. 222 6.5.4 Examples of NP-complete languages.......... 231 Exercises................................. 235 7 Summary 239 Preface This is a free textbook for an undergraduate course on the Theory of Com- putation, which we have been teaching at Carleton University since 2002. Until the 2011/2012 academic year, this course was offered as a second-year course (COMP 2805) and was compulsory for all Computer Science students. Starting with the 2012/2013 academic year, the course has been downgraded to a third-year optional course (COMP 3803). We have been developing this book since we started teaching this course. Currently, we cover most of the material from Chapters 2–5 during a 12-week term with three hours of classes per week. The material from Chapter 6, on Complexity Theory, is taught in the third-year course COMP 3804 (Design and Analysis of Algorithms). In the early years of COMP 2805, we gave a two-lecture overview of Complexity Theory at the end of the term. Even though this overview has disappeared from the course, we decided to keep Chapter 6. This chapter has not been revised/modified for a long time. The course as we teach it today has been influenced by the following two textbooks: Introduction to the Theory of Computation (second edition), by Michael Sipser, Thomson Course Technnology, Boston, 2006. Einführung in die Theoretische Informatik, by Klaus Wagner, Springer- Verlag, Berlin, 1994. Besides reading this text, we recommend that you also take a look at these excellent textbooks, as well as one or more of the following ones: Elements of the Theory of Computation (second edition), by Harry Lewis and Christos Papadimitriou, Prentice-Hall, 1998. viii Introduction to Languages and the Theory of Computation (third edi- tion), by John Martin, McGraw-Hill, 2003. Introduction to Automata Theory, Languages, and Computation (third edition), by John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2007. Please let us know if you find errors, typos, simpler proofs, comments, omissions, or if you think that some parts of the book “need improvement”. Chapter 1 Introduction 1.1 Purpose and motivation This course is on the Theory of Computation, which tries to answer the following questions: What are the mathematical properties of computer hardware and soft- ware? What is a computation and what is an algorithm? Can we give rigorous mathematical definitions of these notions? What are the limitations of computers? Can “everything” be com- puted? (As we will see, the answer to this question is “no”.) Purpose of the Theory of Computation: Develop formal math- ematical models of computation that reflect real-world computers. This field of research was started by mathematicians and logicians in the 1930’s, when they were trying to understand the meaning of a “computation”. A central question asked was whether all mathematical problems can be solved in a systematic way. The research that started in those days led to computers as we know them today. Nowadays, the Theory of Computation can be divided into the follow- ing three areas: Complexity Theory, Computability Theory, and Automata Theory. 2 Chapter 1. Introduction 1.1.1 Complexity theory The main question asked in this area is “What makes some problems com- putationally hard and other problems easy?” Informally, a problem is called “easy”, if it is efficiently solvable. Exam- ples of “easy” problems are (i) sorting a sequence of, say, 1,000,000 numbers, (ii) searching for a name in a telephone directory, and (iii) computing the fastest way to drive from Ottawa to Miami. On the other hand, a problem is called “hard”, if it cannot be solved efficiently, or if we don’t know whether it can be solved efficiently. Examples of “hard” problems are (i) time table scheduling for all courses at Carleton, (ii) factoring a 300-digit integer into its prime factors, and (iii) computing a layout for chips in VLSI. Central Question in Complexity Theory: Classify problems ac- cording to their degree of “difficulty”. Give a rigorous proof that problems that seem to be “hard” are really “hard”. 1.1.2 Computability theory In the 1930’s, Gödel, Turing, and Church discovered that some of the fun- damental mathematical problems cannot be solved by a “computer”. (This may sound strange, because computers were invented only in the 1940’s). An example of such a problem is “Is an arbitrary mathematical statement true or false?” To attack such a problem, we need formal definitions of the notions of computer, algorithm, and computation. The theoretical models that were proposed in order to understand solvable and unsolvable problems led to the development of real computers. Central Question in Computability Theory: Classify problems as being solvable or unsolvable. 1.1. Purpose and motivation 3 1.1.3 Automata theory Automata Theory deals with definitions and properties of different types of “computation models”. Examples of such models are: Finite Automata. These are used in text processing, compilers, and hardware design. Context-Free Grammars. These are used to define programming lan- guages and in Artificial Intelligence. Turing Machines. These form a simple abstract model of a “real” computer, such as your PC at home. Central Question in Automata Theory: Do these models have the same power, or can one model solve more problems than the other? 1.1.4 This course In this course, we will study the last two areas in reverse order: We will start with Automata Theory, followed by Computability Theory. The first area, Complexity Theory, will be covered in COMP 3804. Actually, before we start, we will review some mathematical proof tech- niques. As you may guess, this is a fairly theoretical course, with lots of definitions, theorems, and proofs. You may guess this course is fun stuff for math lovers, but boring and irrelevant for others. You guessed it wrong, and here are the reasons: 1. This course is about the fundamental capabilities and limitations of computers. These topics form the core of computer science. 2. It is about mathematical properties of computer hardware and software. 3. This theory is very much relevant to practice, for example, in the design of new programming languages, compilers, string searching, pattern matching, computer security, artificial intelligence, etc., etc. 4. This course helps you to learn problem solving skills. Theory teaches you how to think, prove, argue, solve problems, express, and abstract. 4 Chapter 1. Introduction 5. This theory simplifies the complex computers to an abstract and simple mathematical model, and helps you to understand them better. 6. This course is about rigorously analyzing capabilities and limitations of systems. Where does this course fit in the Computer Science Curriculum at Car- leton University? It is a theory course that is the third part in the series COMP 1805, COMP 2804, COMP 3803, COMP 3804, and COMP 4804. This course also widens your understanding of computers and will influence other courses including Compilers, Programming Languages, and Artificial Intelligence. 1.2 Mathematical preliminaries Throughout this course, we will assume that you know the following mathe- matical concepts: 1. A set is a collection of well-defined objects. Examples are (i) the set of all Dutch Olympic Gold Medallists, (ii) the set of all pubs in Ottawa, and (iii) the set of all even natural numbers. 2. The set of natural numbers is N = {1, 2, 3,...}. 3. The set of integers is Z = {... , −3, −2, −1, 0, 1, 2, 3,...}. 4. The set of rational numbers is Q = {m/n : m ∈ Z, n ∈ Z, n 6= 0}. 5. The set of real numbers is denoted by R. 6. If A and B are sets, then A is a subset of B, written as A ⊆ B, if every element of A is also an element of B. For example, the set of even natural numbers is a subset of the set of all natural numbers. Every set A is a subset of itself, i.e., A ⊆ A. The empty set is a subset of every set A, i.e., ∅ ⊆ A. 7. If B is a set, then the power set P(B) of B is defined to be the set of all subsets of B: P(B) = {A : A ⊆ B}. Observe that ∅ ∈ P(B) and B ∈ P(B). 1.2. Mathematical preliminaries 5 8. If A and B are two sets, then (a) their union is defined as A ∪ B = {x : x ∈ A or x ∈ B}, (b) their intersection is defined as A ∩ B = {x : x ∈ A and x ∈ B}, (c) their difference is defined as A \ B = {x : x ∈ A and x 6∈ B}, (d) the Cartesian product of A and B is defined as A × B = {(x, y) : x ∈ A and y ∈ B}, (e) the complement of A is defined as A = {x : x 6∈ A}. 9. A binary relation on two sets A and B is a subset of A × B. 10. A function f from A to B, denoted by f : A → B, is a binary relation R, having the property that for each element a ∈ A, there is exactly one ordered pair in R, whose first component is a. We will also say that f (a) = b, or f maps a to b, or the image of a under f is b. The set A is called the domain of f , and the set {b ∈ B : there is an a ∈ A with f (a) = b} is called the range of f. 11. A function f : A → B is one-to-one (or injective), if for any two distinct elements a and a0 in A, we have f (a) 6= f (a0 ). The function f is onto (or surjective), if for each element b ∈ B, there exists an element a ∈ A, such that f (a) = b; in other words, the range of f is equal to the set B. A function f is a bijection, if f is both injective and surjective. 12. A binary relation R ⊆ A × A is an equivalence relation, if it satisfies the following three conditions: 6 Chapter 1. Introduction (a) R is reflexive: For every element in a ∈ A, we have (a, a) ∈ R. (b) R is symmetric: For all a and b in A, if (a, b) ∈ R, then also (b, a) ∈ R. (c) R is transitive: For all a, b, and c in A, if (a, b) ∈ R and (b, c) ∈ R, then also (a, c) ∈ R. 13. A graph G = (V, E) is a pair consisting of a set V , whose elements are called vertices, and a set E, where each element of E is a pair of distinct vertices. The elements of E are called edges. The figure below shows some well-known graphs: K5 (the complete graph on five vertices), K3,3 (the complete bipartite graph on 2 × 3 = 6 vertices), and the Peterson graph. K3,3 K5 Peterson graph The degree of a vertex v, denoted by deg(v), is defined to be the number of edges that are incident on v. A path in a graph is a sequence of vertices that are connected by edges. A path is a cycle, if it starts and ends at the same vertex. A simple path is a path without any repeated vertices. A graph is connected, if there is a path between every pair of vertices. 14. In the context of strings, an alphabet is a finite set, whose elements are called symbols. Examples of alphabets are Σ = {0, 1} and Σ = {a, b, c,... , z}. 15. A string over an alphabet Σ is a finite sequence of symbols, where each symbol is an element of Σ. The length of a string w, denoted by |w|, is the number of symbols contained in w. The empty string, denoted by 1.3. Proof techniques 7 , is the string having length zero. For example, if the alphabet Σ is equal to {0, 1}, then 10, 1000, 0, 101, and  are strings over Σ, having lengths 2, 4, 1, 3, and 0, respectively. 16. A language is a set of strings. 17. The Boolean values are 1 and 0, that represent true and false, respec- tively. The basic Boolean operations include (a) negation (or NOT ), represented by ¬, (b) conjunction (or AND), represented by ∧, (c) disjunction (or OR), represented by ∨, (d) exclusive-or (or XOR), represented by ⊕, (e) equivalence, represented by ↔ or ⇔, (f) implication, represented by → or ⇒. The following table explains the meanings of these operations. NOT AND OR XOR equivalence implication ¬0 = 1 0∧0=0 0∨0=0 0⊕0=0 0↔0=1 0→0=1 ¬1 = 0 0∧1=0 0∨1=1 0⊕1=1 0↔1=0 0→1=1 1∧0=0 1∨0=1 1⊕0=1 1↔0=0 1→0=0 1∧1=1 1∨1=1 1⊕1=0 1↔1=1 1→1=1 1.3 Proof techniques In mathematics, a theorem is a statement that is true. A proof is a sequence of mathematical statements that form an argument to show that a theorem is true. The statements in the proof of a theorem include axioms (assumptions about the underlying mathematical structures), hypotheses of the theorem to be proved, and previously proved theorems. The main question is “How do we go about proving theorems?” This question is similar to the question of how to solve a given problem. Of course, the answer is that finding proofs, or solving problems, is not easy; otherwise life would be dull! There is no specified way of coming up with a proof, but there are some generic strategies that could be of help. In this section, we review some of these strategies, that will be sufficient for this course. The best way to get a feeling of how to come up with a proof is by solving a large number of problems. Here are 8 Chapter 1. Introduction some useful tips. (You may take a look at the book How to Solve It, by G. Pólya). 1. Read and completely understand the statement of the theorem to be proved. Most often this is the hardest part. 2. Sometimes, theorems contain theorems inside them. For example, “Property A if and only if property B”, requires showing two state- ments: (a) If property A is true, then property B is true (A ⇒ B). (b) If property B is true, then property A is true (B ⇒ A). Another example is the theorem “Set A equals set B.” To prove this, we need to prove that A ⊆ B and B ⊆ A. That is, we need to show that each element of set A is in set B, and that each element of set B is in set A. 3. Try to work out a few simple cases of the theorem just to get a grip on it (i.e., crack a few simple cases first). 4. Try to write down the proof once you have it. This is to ensure the correctness of your proof. Often, mistakes are found at the time of writing. 5. Finding proofs takes time, we do not come prewired to produce proofs. Be patient, think, express and write clearly and try to be precise as much as possible. In the next sections, we will go through some of the proof strategies. 1.3.1 Direct proofs As the name suggests, in a direct proof of a theorem, we just approach the theorem directly. Theorem 1.3.1 If n is an odd positive integer, then n2 is odd as well. 1.3. Proof techniques 9 Proof. An odd positive integer n can be written as n = 2k + 1, for some integer k ≥ 0. Then n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1. Since 2(2k 2 + 2k) is even, and “even plus one is odd”, we can conclude that n2 is odd. Theorem 1.3.2 Let G = (V, E) be a graph. Then the sum of the degrees of all vertices is an even integer, i.e., X deg(v) v∈V is even. Proof. If you do not see the meaning of this statement, then first try it out for a few graphs. The reason why the statement holds is very simple: Each edge contributes 2 to the summation (because an edge is incident on exactly two distinct vertices). Actually, the proof above proves the following theorem. Theorem 1.3.3 Let G = (V, E) be a graph. Then the sum of the degrees of all vertices is equal to twice the number of edges, i.e., X deg(v) = 2|E|. v∈V 1.3.2 Constructive proofs This technique not only shows the existence of a certain object, it actually gives a method of creating it. Here is how a constructive proof looks like: Theorem 1.3.4 There exists an object with property P. Proof. Here is the object: [...] And here is the proof that the object satisfies property P: [...] Here is an example of a constructive proof. A graph is called 3-regular, if each vertex has degree three. 10 Chapter 1. Introduction Theorem 1.3.5 For every even integer n ≥ 4, there exists a 3-regular graph with n vertices. Proof. Define V = {0, 1, 2,... , n − 1}, and E = {{i, i+1} : 0 ≤ i ≤ n−2}∪{{n−1, 0}}∪{{i, i+n/2} : 0 ≤ i ≤ n/2−1}. Then the graph G = (V, E) is 3-regular. Convince yourself that this graph is indeed 3-regular. It may help to draw the graph for, say, n = 8. 1.3.3 Nonconstructive proofs In a nonconstructive proof, we show that a certain object exists, without actually creating it. Here is an example of such a proof: Theorem 1.3.6 There exist irrational numbers x and y such that xy is ra- tional. Proof. There are two possible cases. √ √2 Case 1: 2 ∈ Q. √ In√this case, we take x = y = 2. In Theorem 1.3.9 below, we will prove that 2 is irrational. √ √2 Case 2: 2 6∈ Q. √ √2 √ In this case, we take x = 2 and y = 2. Since √  √2 √ √  2 2 xy = 2 = 2 = 2, the claim in the theorem follows. Observe that this proof indeed proves the theorem, but it does not give an example of a pair of irrational numbers x and y such that xy is rational. 1.3. Proof techniques 11 1.3.4 Proofs by contradiction This is how a proof by contradiction looks like: Theorem 1.3.7 Statement S is true. Proof. Assume that statement S is false. Then, derive a contradiction (such as 1 + 1 = 3). In other words, show that the statement “¬S ⇒ false” is true. This is sufficient, because the contrapositive of the statement “¬S ⇒ false” is the statement “true ⇒ S”. The latter logical formula is equivalent to S, and that is what we wanted to show. Below, we give two examples of proofs by contradiction. Theorem 1.3.8 Let n be a positive integer. If n2 is even, then n is even. Proof. We will prove the theorem by contradiction. So we assume that n2 is even, but n is odd. Since n is odd, we know from Theorem 1.3.1 that n2 is odd. This is a contradiction, because we assumed that n2 is even. √ √ Theorem 1.3.9 2 is irrational, i.e., 2 cannot be written as a fraction of two integers m and n. √ Proof. We will prove√ the theorem by contradiction. So we assume √ that 2 is rational. Then 2 can be written as a fraction of two integers, 2 = m/n, where m ≥ 1 and n ≥ 1. We may assume that m and n do not share any common factors, i.e., the greatest common divisor of m and n is equal to one; if this √ is not the case, then we can get rid of the common factors. By squaring 2 = m/n, we get 2n2 = m2. This implies that m2 is even. Then, by Theorem 1.3.8, m is even, which means that we can write m as m = 2k, for some positive integer k. It follows that 2n2 = m2 = 4k 2 , which implies that n2 = 2k 2. Hence, n2 is even. Again by Theorem 1.3.8, it follows that n is even. We have shown that m and n are both even. But we know that m and n √ are not both even. Hence, we have a contradiction.√Our assumption that 2 is rational is wrong. Thus, we can conclude that 2 is irrational. There is a nice discussion of this proof in the book My Brain is Open: The Mathematical Journeys of Paul Erdős by B. Schechter. 12 Chapter 1. Introduction 1.3.5 The pigeon hole principle This is a simple principle with surprising consequences. Pigeon Hole Principle: If n + 1 or more objects are placed into n boxes, then there is at least one box containing two or more objects. In other words, if A and B are two sets such that |A| > |B|, then there is no one-to-one function from A to B. Theorem 1.3.10 Let n be a positive integer. Every sequence of n2 + 1 dis- tinct real numbers contains a subsequence of length n + 1 that is either in- creasing or decreasing. Proof. For example consider the sequence (20, 10, 9, 7, 11, 2, 21, 1, 20, 31) of 10 = 32 + 1 numbers. This sequence contains an increasing subsequence of length 4 = 3 + 1, namely (10, 11, 21, 31). The proof of this theorem is by contradiction, and uses the pigeon hole principle. Let (a1 , a2 ,... , an2 +1 ) be an arbitrary sequence of n2 + 1 distinct real numbers. For each i with 1 ≤ i ≤ n2 + 1, let inc i denote the length of the longest increasing subsequence that starts at ai , and let dec i denote the length of the longest decreasing subsequence that starts at ai. Using this notation, the claim in the theorem can be formulated as follows: There is an index i such that inc i ≥ n + 1 or dec i ≥ n + 1. We will prove the claim by contradiction. So we assume that inc i ≤ n and dec i ≤ n for all i with 1 ≤ i ≤ n2 + 1. Consider the set B = {(b, c) : 1 ≤ b ≤ n, 1 ≤ c ≤ n}, and think of the elements of B as being boxes. For each i with 1 ≤ i ≤ n2 +1, the pair (inc i , dec i ) is an element of B. So we have n2 +1 elements (inc i , dec i ), which are placed in the n2 boxes of B. By the pigeon hole principle, there must be a box that contains two (or more) elements. In other words, there exist two integers i and j such that i < j and (inc i , dec i ) = (inc j , dec j ). Recall that the elements in the sequence are distinct. Hence, ai 6= aj. We consider two cases. 1.3. Proof techniques 13 First assume that ai < aj. Then the length of the longest increasing subsequence starting at ai must be at least 1+inc j , because we can append ai to the longest increasing subsequence starting at aj. Therefore, inc i 6= inc j , which is a contradiction. The second case is when ai > aj. Then the length of the longest decreasing subsequence starting at ai must be at least 1+dec j , because we can append ai to the longest decreasing subsequence starting at aj. Therefore, dec i 6= dec j , which is again a contradiction. 1.3.6 Proofs by induction This is a very powerful and important technique for proving theorems. For each positive integer n, let P (n) be a mathematical statement that depends on n. Assume we wish to prove that P (n) is true for all positive integers n. A proof by induction of such a statement is carried out as follows: Basis: Prove that P (1) is true. Induction step: Prove that for all n ≥ 1, the following holds: If P (n) is true, then P (n + 1) is also true. In the induction step, we choose an arbitrary integer n ≥ 1 and assume that P (n) is true; this is called the induction hypothesis. Then we prove that P (n + 1) is also true. Theorem 1.3.11 For all positive integers n, we have n(n + 1) 1 + 2 + 3 +... + n =. 2 Proof. We start with the basis of the induction. If n = 1, then the left-hand side is equal to 1, and so is the right-hand side. So the theorem is true for n = 1. For the induction step, let n ≥ 1 and assume that the theorem is true for n, i.e., assume that n(n + 1) 1 + 2 + 3 +... + n =. 2 14 Chapter 1. Introduction We have to prove that the theorem is true for n + 1, i.e., we have to prove that (n + 1)(n + 2) 1 + 2 + 3 +... + (n + 1) =. 2 Here is the proof: 1 + 2 + 3 +... + (n + 1) = |1 + 2 + 3{z+... + n} +(n + 1) n(n+1) = 2 n(n + 1) = + (n + 1) 2 (n + 1)(n + 2) =. 2 By the way, here is an alternative proof of the theorem above: Let S = 1 + 2 + 3 +... + n. Then, S = 1 + 2 + 3 +... + (n − 2) + (n − 1) + n S = n + (n − 1) + (n − 2) +... + 3 + 2 + 1 2S = (n + 1) + (n + 1) + (n + 1) +... + (n + 1) + (n + 1) + (n + 1) Since there are n terms on the right-hand side, we have 2S = n(n + 1). This implies that S = n(n + 1)/2. Theorem 1.3.12 For every positive integer n, a − b is a factor of an − bn. Proof. A direct proof can be given by providing a factorization of an − bn : an − bn = (a − b)(an−1 + an−2 b + an−3 b2 +... + abn−2 + bn−1 ). We now prove the theorem by induction. For the basis, let n = 1. The claim in the theorem is “a − b is a factor of a − b”, which is obviously true. Let n ≥ 1 and assume that a − b is a factor of an − bn. We have to prove that a − b is a factor of an+1 − bn+1. We have an+1 − bn+1 = an+1 − an b + an b − bn+1 = an (a − b) + (an − bn )b. The first term on the right-hand side is divisible by a − b. By the induction hypothesis, the second term on the right-hand side is divisible by a − b as well. Therefore, the entire right-hand side is divisible by a − b. Since the right-hand side is equal to an+1 − bn+1 , it follows that a − b is a factor of an+1 − bn+1. We now give an alternative proof of Theorem 1.3.3: 1.3. Proof techniques 15 Theorem 1.3.13 Let G = (V, E) be a graph with m edges. Then the sum of the degrees of all vertices is equal to twice the number of edges, i.e., X deg(v) = 2m. v∈V Proof. The proof is by induction on the number m of edges. For the basis of the induction, assumePthat m = 0. Then the graph G does not contain any edges and, therefore, v∈V deg(v) = 0. Thus, the theorem is true if m = 0. Let m ≥ 0 and assume that the theorem is true for every graph with m edges. P Let G be an arbitrary graph with m + 1 edges. We have to prove that v∈V deg(v) = 2(m + 1). Let {a, b} be an arbitrary edge in G, and let G0 be the graph obtained from G by removing the edge {a, b}. Since G0 has m edges, we know from the induction hypothesis that the sum of the degrees of all vertices in G0 is equal to 2m. Using this, we obtain X X deg(v) = deg(v) + 2 = 2m + 2 = 2(m + 1). v∈G v∈G0 1.3.7 More examples of proofs Recall Theorem 1.3.5, which states that for every even integer n ≥ 4, there exists a 3-regular graph with n vertices. The following theorem explains why we stated this theorem for even values of n. Theorem 1.3.14 Let n ≥ 5 be an odd integer. There is no 3-regular graph with n vertices. Proof. The proof is by contradiction. So we assume that there exists a graph G = (V, E) with n vertices that is 3-regular. Let m be the number of edges in G. Since deg(v) = 3 for every vertex, we have X deg(v) = 3n. v∈V On the other hand, by Theorem 1.3.3, we have X deg(v) = 2m. v∈V 16 Chapter 1. Introduction It follows that 3n = 2m, which can be rewritten as m = 3n/2. Since m is an integer, and since gcd (2, 3) = 1, n/2 must be an integer. Hence, n is even, which is a contradiction. Let Kn be the complete graph on n vertices. This graph has a vertex set of size n, and every pair of distinct vertices is joined by an edge. If G = (V, E) is a graph with n vertices, then the complement G of G is the graph with vertex set V that consists of those edges of Kn that are not present in G. Theorem 1.3.15 Let n ≥ 2 and let G be a graph on n vertices. Then G is connected or G is connected. Proof. We prove the theorem by induction on the number n of vertices. For the basis, assume that n = 2. There are two possibilities for the graph G: 1. G contains one edge. In this case, G is connected. 2. G does not contain an edge. In this case, the complement G contains one edge and, therefore, G is connected. So for n = 2, the theorem is true. Let n ≥ 2 and assume that the theorem is true for every graph with n vertices. Let G be graph with n + 1 vertices. We have to prove that G is connected or G is connected. We consider three cases. Case 1: There is a vertex v whose degree in G is equal to n. Since G has n+1 vertices, v is connected by an edge to every other vertex of G. Therefore, G is connected. Case 2: There is a vertex v whose degree in G is equal to 0. In this case, the degree of v in the graph G is equal to n. Since G has n+1 vertices, v is connected by an edge to every other vertex of G. Therefore, G is connected. Case 3: For every vertex v, the degree of v in G is in {1, 2,... , n − 1}. Let v be an arbitrary vertex of G. Let G0 be the graph obtained by deleting from G the vertex v, together with all edges that are incident on v. Since G0 has n vertices, we know from the induction hypothesis that G0 is connected or G0 is connected. 1.3. Proof techniques 17 Let us first assume that G0 is connected. Then the graph G is connected as well, because there is at least one edge in G between v and some vertex of G0. If G0 is not connected, then G0 must be connected. Since we are in Case 3, we know that the degree of v in G is in the set {1, 2,... , n − 1}. It follows that the degree of v in the graph G is in this set as well. Hence, there is at least one edge in G between v and some vertex in G0. This implies that G is connected. The previous theorem can be rephrased as follows: Theorem 1.3.16 Let n ≥ 2 and consider the complete graph Kn on n ver- tices. Color each edge of this graph as either red or blue. Let R be the graph consisting of all the red edges, and let B be the graph consisting of all the blue edges. Then R is connected or B is connected. A graph is said to be planar, if it can be drawn (a better term is “embed- ded”) in the plane in such a way that no two edges intersect, except possibly at their endpoints. An embedding of a planar graph consists of vertices, edges, and faces. In the example below, there are 11 vertices, 18 edges, and 9 faces (including the unbounded face). The following theorem is known as Euler’s theorem for planar graphs. Apparently, this theorem was discovered by Euler around 1750. Legendre gave the first proof in 1794, see http://www.ics.uci.edu/~eppstein/junkyard/euler/ Theorem 1.3.17 (Euler) Consider an embedding of a planar graph G. Let v, e, and f be the number of vertices, edges, and faces (including the single 18 Chapter 1. Introduction unbounded face) of this embedding, respectively. Moreover, let c be the number of connected components of G. Then v − e + f = c + 1. Proof. The proof is by induction on the number of edges of G. To be more precise, we start with a graph having no edges, and prove that the theorem holds for this case. Then, we add the edges one by one, and show that the relation v − e + f = c + 1 is maintained. So we first assume that G has no edges, i.e., e = 0. Then the embedding consists of a collection of v points. In this case, we have f = 1 and c = v. Hence, the relation v − e + f = c + 1 holds. Let e > 0 and assume that Euler’s formula holds for a subgraph of G having e − 1 edges. Let {u, v} be an edge of G that is not in the subgraph, and add this edge to the subgraph. There are two cases depending on whether this new edge joins two connected components or joins two vertices in the same connected component. Case 1: The new edge {u, v} joins two connected components. In this case, the number of vertices and the number of faces do not change, the number of connected components goes down by 1, and the number of edges increases by 1. It follows that the relation in the theorem is still valid. Case 2: The new edge {u, v} joins two vertices in the same connected com- ponent. In this case, the number of vertices and the number of connected com- ponents do not change, the number of edges increases by 1, and the number of faces increases by 1 (because the new edge splits one face into two faces). Therefore, the relation in the theorem is still valid. Euler’s theorem is usually stated as follows: Theorem 1.3.18 (Euler) Consider an embedding of a connected planar graph G. Let v, e, and f be the number of vertices, edges, and faces (in- cluding the single unbounded face) of this embedding, respectively. Then v − e + f = 2. If you like surprising proofs of various mathematical results, you should read the book Proofs from THE BOOK by Aigner and Ziegler. Exercises 19 Exercises 1.1 Use induction to prove that every integer n ≥ 2 can be written as a product of prime numbers. √ 1.2 For every prime number p, prove that p is irrational. √ 1.3 Let n be a positive integer that is not a perfect square. Prove that n is irrational. 1.4 Prove by induction that n4 − 4n2 is divisible by 3, for all integers n ≥ 1. 1.5 Prove that n X 1 2 < 2 − 1/n, i=1 i for every integer n ≥ 2. 1.6 Prove that 9 divides n3 + (n + 1)3 + (n + 2)3 , for every integer n ≥ 0. 1.7 Prove that in any set of n + 1 numbers from {1, 2,... , 2n}, there are always two numbers that are consecutive. 1.8 Prove that in any set of n + 1 numbers from {1, 2,... , 2n}, there are always two numbers such that one divides the other. 20 Chapter 1. Introduction Chapter 2 Finite Automata and Regular Languages In this chapter, we introduce and analyze the class of languages that are known as regular languages. Informally, these languages can be “processed” by computers having a very small amount of memory. 2.1 An example: Controling a toll gate Before we give a formal definition of a finite automaton, we consider an example in which such an automaton shows up in a natural way. We consider the problem of designing a “computer” that controls a toll gate. When a car arrives at the toll gate, the gate is closed. The gate opens as soon as the driver has payed 25 cents. We assume that we have only three coin denominations: 5, 10, and 25 cents. We also assume that no excess change is returned. After having arrived at the toll gate, the driver inserts a sequence of coins into the machine. At any moment, the machine has to decide whether or not to open the gate, i.e., whether or not the driver has paid 25 cents (or more). In order to decide this, the machine is in one of the following six states, at any moment during the process: The machine is in state q0 , if it has not collected any money yet. The machine is in state q1 , if it has collected exactly 5 cents. The machine is in state q2 , if it has collected exactly 10 cents. 22 Chapter 2. Finite Automata and Regular Languages The machine is in state q3 , if it has collected exactly 15 cents. The machine is in state q4 , if it has collected exactly 20 cents. The machine is in state q5 , if it has collected 25 cents or more. Initially (when a car arrives at the toll gate), the machine is in state q0. Assume, for example, that the driver presents the sequence (10,5,5,10) of coins. After receiving the first 10 cents coin, the machine switches from state q0 to state q2. After receiving the first 5 cents coin, the machine switches from state q2 to state q3. After receiving the second 5 cents coin, the machine switches from state q3 to state q4. After receiving the second 10 cents coin, the machine switches from state q4 to state q5. At this moment, the gate opens. (Remember that no change is given.) The figure below represents the behavior of the machine for all possible sequences of coins. State q5 is represented by two circles, because it is a special state: As soon as the machine reaches this state, the gate opens. 5, 10, 25 10 10 10 10, 25 start 5 5 5 5 5, 10 q0 q1 q2 q3 q4 q5 25 25 25 25 Observe that the machine (or computer) only has to remember which state it is in at any given time. Thus, it needs only a very small amount of memory: It has to be able to distinguish between any one of six possible cases and, therefore, it only needs a memory of dlog 6e = 3 bits. 2.2. Deterministic finite automata 23 2.2 Deterministic finite automata Let us look at another example. Consider the following state diagram: 0 1 0 1 q1 q2 q3 0, 1 We say that q1 is the start state and q2 is an accept state. Consider the input string 1101. This string is processed in the following way: Initially, the machine is in the start state q1. After having read the first 1, the machine switches from state q1 to state q2. After having read the second 1, the machine switches from state q2 to state q2. (So actually, it does not switch.) After having read the first 0, the machine switches from state q2 to state q3. After having read the third 1, the machine switches from state q3 to state q2. After the entire string 1101 has been processed, the machine is in state q2 , which is an accept state. We say that the string 1101 is accepted by the machine. Consider now the input string 0101010. After having read this string from left to right (starting in the start state q1 ), the machine is in state q3. Since q3 is not an accept state, we say that the machine rejects the string 0101010. We hope you are able to see that this machine accepts every binary string that ends with a 1. In fact, the machine accepts more strings: Every binary string having the property that there are an even number of 0s following the rightmost 1, is accepted by this machine. 24 Chapter 2. Finite Automata and Regular Languages Every other binary string is rejected by the machine. Observe that each such string is either empty, consists of 0s only, or has an odd number of 0s following the rightmost 1. We now come to the formal definition of a finite automaton: Definition 2.2.1 A finite automaton is a 5-tuple M = (Q, Σ, δ, q, F ), where 1. Q is a finite set, whose elements are called states, 2. Σ is a finite set, called the alphabet; the elements of Σ are called symbols, 3. δ : Q × Σ → Q is a function, called the transition function, 4. q is an element of Q; it is called the start state, 5. F is a subset of Q; the elements of F are called accept states. You can think of the transition function δ as being the “program” of the finite automaton M = (Q, Σ, δ, q, F ). This function tells us what M can do in “one step”: Let r be a state of Q and let a be a symbol of the alphabet Σ. If the finite automaton M is in state r and reads the symbol a, then it switches from state r to state δ(r, a). (In fact, δ(r, a) may be equal to r.) The “computer” that we designed in the toll gate example in Section 2.1 is a finite automaton. For this example, we have Q = {q0 , q1 , q2 , q3 , q4 , q5 }, Σ = {5, 10, 25}, the start state is q0 , F = {q5 }, and δ is given by the following table: 5 10 25 q0 q1 q2 q5 q1 q2 q3 q5 q2 q3 q4 q5 q3 q4 q5 q5 q4 q5 q5 q5 q5 q5 q5 q5 The example given in the beginning of this section is also a finite automa- ton. For this example, we have Q = {q1 , q2 , q3 }, Σ = {0, 1}, the start state is q1 , F = {q2 }, and δ is given by the following table: 2.2. Deterministic finite automata 25 0 1 q1 q1 q2 q2 q3 q2 q3 q2 q2 Let us denote this finite automaton by M. The language of M , denoted by L(M ), is the set of all binary strings that are accepted by M. As we have seen before, we have L(M ) = {w : w contains at least one 1 and ends with an even number of 0s}. We now give a formal definition of the language of a finite automaton: Definition 2.2.2 Let M = (Q, Σ, δ, q, F ) be a finite automaton and let w = w1 w2... wn be a string over Σ. Define the sequence r0 , r1 ,... , rn of states, in the following way: r0 = q, ri+1 = δ(ri , wi+1 ), for i = 0, 1,... , n − 1. 1. If rn ∈ F , then we say that M accepts w. 2. If rn 6∈ F , then we say that M rejects w. In this definition, w may be the empty string, which we denote by , and whose length is zero; thus in the definition above, n = 0. In this case, the sequence r0 , r1 ,... , rn of states has length one; it consists of just the state r0 = q. The empty string is accepted by M if and only if the start state q belongs to F. Definition 2.2.3 Let M = (Q, Σ, δ, q, F ) be a finite automaton. The lan- guage L(M ) accepted by M is defined to be the set of all strings that are accepted by M : L(M ) = {w : w is a string over Σ and M accepts w }. Definition 2.2.4 A language A is called regular, if there exists a finite au- tomaton M such that A = L(M ). 26 Chapter 2. Finite Automata and Regular Languages We finish this section by presenting an equivalent way of defining the language accepted by a finite automaton. Let M = (Q, Σ, δ, q, F ) be a finite automaton. The transition function δ : Q × Σ → Q tells us that, when M is in state r ∈ Q and reads symbol a ∈ Σ, it switches from state r to state δ(r, a). Let Σ∗ denote the set of all strings over the alphabet Σ. (Σ∗ includes the empty string .) We extend the function δ to a function δ : Q × Σ∗ → Q, that is defined as follows. For any state r ∈ Q and for any string w over the alphabet Σ,  r if w = , δ(r, w) = δ(δ(r, v), a) if w = va, where v is a string and a ∈ Σ. What is the meaning of this function δ? Let r be a state of Q and let w be a string over the alphabet Σ. Then δ(r, w) is the state that M reaches, when it starts in state r, reads the string w from left to right, and uses δ to switch from state to state. Using this notation, we have L(M ) = {w : w is a string over Σ and δ(q, w) ∈ F }. 2.2.1 A first example of a finite automaton Let A = {w : w is a binary string containing an odd number of 1s}. We claim that this language A is regular. In order to prove this, we have to construct a finite automaton M such that A = L(M ). How to construct M ? Here is a first idea: The finite automaton reads the input string w from left to right and keeps track of the number of 1s it has seen. After having read the entire string w, it checks whether this number is odd (in which case w is accepted) or even (in which case w is rejected). Using this approach, the finite automaton needs a state for every integer i ≥ 0, indicating that the number of 1s read so far is equal to i. Hence, to design a finite automaton that follows this approach, we need an infinite 2.2. Deterministic finite automata 27 number of states. But, the definition of finite automaton requires the number of states to be finite. A better, and correct approach, is to keep track of whether the number of 1s read so far is even or odd. This leads to the following finite automaton: The set of states is Q = {qe , qo }. If the finite automaton is in state qe , then it has read an even number of 1s; if it is in state qo , then it has read an odd number of 1s. The alphabet is Σ = {0, 1}. The start state is qe , because at the start, the number of 1s read by the automaton is equal to 0, and 0 is even. The set F of accept states is F = {qo }. The transition function δ is given by the following table: 0 1 qe qe qo qo qo qe This finite automaton M = (Q, Σ, δ, qe , F ) can also be described by its state diagram, which is given in the figure below. The arrow that comes “out of the blue” and enters the state qe , indicates that qe is the start state. The state depicted with double circles indicates the accept state. 0 1 qe qo 0 1 We have constructed a finite automaton M that accepts the language A. Therefore, A is a regular language. 28 Chapter 2. Finite Automata and Regular Languages 2.2.2 A second example of a finite automaton Define the language A as A = {w : w is a binary string containing 101 as a substring}. Again, we claim that A is a regular language. In other words, we claim that there exists a finite automaton M that accepts A, i.e., A = L(M ). The finite automaton M will do the following, when reading an input string from left to right: It skips over all 0s, and stays in the start state. At the first 1, it switches to the state “maybe the next two symbols are 01”. – If the next symbol is 1, then it stays in the state “maybe the next two symbols are 01”. – On the other hand, if the next symbol is 0, then it switches to the state “maybe the next symbol is 1”. ∗ If the next symbol is indeed 1, then it switches to the accept state (but keeps on reading until the end of the string). ∗ On the other hand, if the next symbol is 0, then it switches to the start state, and skips 0s until it reads 1 again. By defining the following four states, this process will become clear: q1 : M is in this state if the last symbol read was 1, but the substring 101 has not been read. q10 : M is in this state if the last two symbols read were 10, but the substring 101 has not been read. q101 : M is in this state if the substring 101 has been read in the input string. q: In all other cases, M is in this state. Here is the formal description of the finite automaton that accepts the language A: Q = {q, q1 , q10 , q101 }, 2.2. Deterministic finite automata 29 Σ = {0, 1}, the start state is q, the set F of accept states is equal to F = {q101 }, and the transition function δ is given by the following table: 0 1 q q q1 q1 q10 q1 q10 q q101 q101 q101 q101 The figure below gives the state diagram of the finite automaton M = (Q, Σ, δ, q, F ). 0 1 1 q q1 0 0 q10 q101 0, 1 1 This finite automaton accepts the language A consisting of all binary strings that contain the substring 101. As an exercise, how would you obtain a finite automaton that accepts the complement of A, i.e., the language consisting of all binary strings that do not contain the substring 101? 2.2.3 A third example of a finite automaton The finite automata we have seen so far have exactly one accept state. In this section, we will see an example of a finite automaton having more accept states. 30 Chapter 2. Finite Automata and Regular Languages Let A be the language A = {w ∈ {0, 1}∗ : w has a 1 in the third position from the right}, where {0, 1}∗ is the set of all binary strings, including the empty string . We claim that A is a regular language. To prove this, we have to construct a finite automaton M such that A = L(M ). At first sight, it seems difficult (or even impossible?) to construct such a finite automaton: How does the automaton “know” that it has reached the third symbol from the right? It is, however, possible to construct such an automaton. The main idea is to remember the last three symbols that have been read. Thus, the finite automaton has eight states qijk , where i, j, and k range over the two elements of {0, 1}. If the automaton is in state qijk , then the following hold: If M has read at least three symbols, then the three most recently read symbols are ijk. If M has read only two symbols, then these two symbols are jk; more- over, i = 0. If M has read only one symbol, then this symbol is k; moreover, i = j = 0. If M has not read any symbol, then i = j = k = 0. The start state is q000 and the set of accept states is {q100 , q110 , q101 , q111 }. The transition function of M is given by the following state diagram. 0 0 q000 0 q100 0 q010 q110 1 1 1 0 1 0 0 0 q001 q101 q011 q111 1 1 1 1 2.3. Regular operations 31 2.3 Regular operations In this section, we define three operations on languages. Later, we will answer the question whether the set of all regular languages is closed under these operations. Let A and B be two languages over the same alphabet. 1. The union of A and B is defined as A ∪ B = {w : w ∈ A or w ∈ B}. 2. The concatenation of A and B is defined as AB = {ww0 : w ∈ A and w0 ∈ B}. In words, AB is the set of all strings obtained by taking an arbitrary string w in A and an arbitrary string w0 in B, and gluing them together (such that w is to the left of w0 ). 3. The star of A is defined as A∗ = {u1 u2... uk : k ≥ 0 and ui ∈ A for all i = 1, 2,... , k}. In words, A∗ is obtained by taking any finite number of strings in A, and gluing them together. Observe that k = 0 is allowed; this corresponds to the empty string . Thus,  ∈ A∗. To give an example, let A = {0, 01} and B = {1, 10}. Then A ∪ B = {0, 01, 1, 10}, AB = {01, 010, 011, 0110}, and A∗ = {, 0, 01, 00, 001, 010, 0101, 000, 0001, 00101,...}. As another example, if Σ = {0, 1}, then Σ∗ is the set of all binary strings (including the empty string). Observe that a string always has a finite length. Before we proceed, we give an alternative (and equivalent) definition of the star of the language A: Define A0 = {} 32 Chapter 2. Finite Automata and Regular Languages and, for k ≥ 1, Ak = AAk−1 , i.e., Ak is the concatenation of the two languages A and Ak−1. Then we have ∞ [ ∗ A = Ak. k=0 Theorem 2.3.1 The set of regular languages is closed under the union op- eration, i.e., if A and B are regular languages over the same alphabet Σ, then A ∪ B is also a regular language. Proof. Since A and B are regular languages, there are finite automata M1 = (Q1 , Σ, δ1 , q1 , F1 ) and M2 = (Q2 , Σ, δ2 , q2 , F2 ) that accept A and B, respectively. In order to prove that A ∪ B is regular, we have to construct a finite automaton M that accepts A ∪ B. In other words, M must have the property that for every string w ∈ Σ∗ , M accepts w ⇔ M1 accepts w or M2 accepts w. As a first idea, we may think that M could do the following: Starting in the start state q1 of M1 , M “runs” M1 on w. If, after having read w, M1 is in a state of F1 , then w ∈ A, thus w ∈ A ∪ B and, therefore, M accepts w. On the other hand, if, after having read w, M1 is in a state that is not in F1 , then w 6∈ A and M “runs” M2 on w, starting in the start state q2 of M2. If, after having read w, M2 is in a state of F2 , then we know that w ∈ B, thus w ∈ A ∪ B and, therefore, M accepts w. Otherwise, we know that w 6∈ A ∪ B, and M rejects w. This idea does not work, because the finite automaton M can read the input string w only once. The correct approach is to run M1 and M2 simulta- neously. We define the set Q of states of M to be the Cartesian product Q1 × Q2. If M is in state (r1 , r2 ), this means that if M1 would have read the input string up to this point, then it would be in state r1 , and 2.3. Regular operations 33 if M2 would have read the input string up to this point, then it would be in state r2. This leads to the finite automaton M = (Q, Σ, δ, q, F ), where Q = Q1 × Q2 = {(r1 , r2 ) : r1 ∈ Q1 and r2 ∈ Q2 }. Observe that |Q| = |Q1 | × |Q2 |, which is finite. Σ is the alphabet of A and B (recall that we assume that A and B are languages over the same alphabet). The start state q of M is equal to q = (q1 , q2 ). The set F of accept states of M is given by F = {(r1 , r2 ) : r1 ∈ F1 or r2 ∈ F2 } = (F1 × Q2 ) ∪ (Q1 × F2 ). The transition function δ : Q × Σ → Q is given by δ((r1 , r2 ), a) = (δ1 (r1 , a), δ2 (r2 , a)), for all r1 ∈ Q1 , r2 ∈ Q2 , and a ∈ Σ. To finish the proof, we have to show that this finite automaton M indeed accepts the language A ∪ B. Intuitively, this should be clear from the discus- sion above. The easiest way to give a formal proof is by using the extended transition functions δ1 and δ2. (The extended transition function has been defined after Definition 2.2.4.) Here we go: Recall that we have to prove that M accepts w ⇔ M1 accepts w or M2 accepts w, i.e, M accepts w ⇔ δ1 (q1 , w) ∈ F1 or δ2 (q2 , w) ∈ F2. In terms of the extended transition function δ of the transition function δ of M , this becomes δ((q1 , q2 ), w) ∈ F ⇔ δ1 (q1 , w) ∈ F1 or δ2 (q2 , w) ∈ F2. (2.1) By applying the definition of the extended transition function, as given after Definition 2.2.4, to δ, it can be seen that δ((q1 , q2 ), w) = (δ1 (q1 , w), δ2 (q2 , w)). 34 Chapter 2. Finite Automata and Regular Languages The latter equality implies that (2.1) is true and, therefore, M indeed accepts the language A ∪ B. What about the closure of the regular languages under the concatenation and star operations? It turns out that the regular languages are closed under these operations. But how do we prove this? Let A and B be two regular languages, and let M1 and M2 be finite automata that accept A and B, respectively. How do we construct a finite automaton M that accepts the concatenation AB? Given an input string u, M has to decide whether or not u can be broken into two strings w and w0 (i.e., write u as u = ww0 ), such that w ∈ A and w0 ∈ B. In words, M has to decide whether or not u can be broken into two substrings, such that the first substring is accepted by M1 and the second substring is accepted by M2. The difficulty is caused by the fact that M has to make this decision by scanning the string u only once. If u ∈ AB, then M has to decide, during this single scan, where to break u into two substrings. Similarly, if u 6∈ AB, then M has to decide, during this single scan, that u cannot be broken into two substrings such that the first substring is in A and the second substring is in B. It seems to be even more difficult to prove that A∗ is a regular language, if A itself is regular. In order to prove this, we need a finite automaton that, when given an arbitrary input string u, decides whether or not u can be broken into substrings such that each substring is in A. The problem is that, if u ∈ A∗ , the finite automaton has to determine into how many substrings, and where, the string u has to be broken; it has to do this during one single scan of the string u. As we mentioned already, if A and B are regular languages, then both AB and A∗ are also regular. In order to prove these claims, we will introduce a more general type of finite automaton. The finite automata that we have seen so far are deterministic. This means the following: If the finite automaton M is in state r and if it reads the symbol a, then M switches from state r to the uniquely defined state δ(r, a). From now on, we will call such a finite automaton a deterministic finite automaton (DFA). In the next section, we will define the notion of a nonde- terministic finite automaton (NFA). For such an automaton, there are zero or more possible states to switch to. At first sight, nondeterministic finite 2.4. Nondeterministic finite automata 35 automata seem to be more powerful than their deterministic counterparts. We will prove, however, that DFAs have the same power as NFAs. As we will see, using this fact, it will be easy to prove that the class of regular languages is closed under the concatenation and star operations. 2.4 Nondeterministic finite automata We start by giving three examples of nondeterministic finite automata. These examples will show the difference between this type of automata and the deterministic versions that we have considered in the previous sections. After these examples, we will give a formal definition of a nondeterministic finite automaton. 2.4.1 A first example Consider the following state diagram: 0, 1 1 0, ε 1 q1 q2 q3 q4 0, 1 You will notice three differences with the finite automata that we have seen until now. First, if the automaton is in state q1 and reads the symbol 1, then it has two options: Either it stays in state q1 , or it switches to state q2. Second, if the automaton is in state q2 , then it can switch to state q3 without reading a symbol ; this is indicated by the edge having the empty string  as label. Third, if the automaton is in state q3 and reads the symbol 0, then it cannot continue. Let us see what this automaton can do when it gets the string 010110 as input. Initially, the automaton is in the start state q1. Since the first symbol in the input string is 0, the automaton stays in state q1 after having read this symbol. The second symbol is 1, and the automaton can either stay in state q1 or switch to state q2. 36 Chapter 2. Finite Automata and Regular Languages – If the automaton stays in state q1 , then it is still in this state after having read the third symbol. – If the automaton switches to state q2 , then it again has two op- tions: ∗ Either read the third symbol in the input string, which is 0, and switch to state q3 , ∗ or switch to state q3 , without reading the third symbol. If we continue in this way, then we see that, for the input string 010110, there are seven possible computations. All these computations are given in the figure below. 0 q1 q1 1 q1 0 q3 1 1 q2 ε 0 q3 hang q1 q1 1 q2 hang 1 ε 0 q3 1 q4 q4 q1 0 q1 q3 1 q4 1 q4 0 q4 1 0 q2 q3 hang ε Consider the lowest path in the figure above: When reading the first symbol, the automaton stays in state q1. When reading the second symbol, the automaton switches to state q2. The automaton does not read the third symbol (equivalently, it “reads” the empty string ), and switches to state q3. At this moment, the 2.4. Nondeterministic finite automata 37 automaton cannot continue: The third symbol is 0, but there is no edge leaving q3 that is labeled 0, and there is no edge leaving q3 that is labeled . Therefore, the computation hangs at this point. From the figure, you can see that, out of the seven possible computations, exactly two end in the accept state q4 (after the entire input string 010110 has been read). We say that the automaton accepts the string 010110, because there is at least one computation that ends in the accept state. Now consider the input string 010. In this case, there are three possible computations: 0 1 0 1. q1 → q1 → q1 → q1 0 1 0 2. q1 → q1 → q2 → q3 0 1  3. q1 → q1 → q2 → q3 → hang None of these computations ends in the accept state (after the entire input string 010 has been read). Therefore, we say that the automaton rejects the input string 010. The state diagram given above is an example of a nondeterministic finite automaton (NFA). Informally, an NFA accepts a string, if there exists at least one path in the state diagram that (i) starts in the start state, (ii) does not hang before the entire string has been read, and (iii) ends in an accept state. A string for which (i), (ii), and (iii) does not hold is rejected by the NFA. The NFA given above accepts all binary strings that contain 101 or 11 as a substring. All other binary strings are rejected. 2.4.2 A second example Let A be the language A = {w ∈ {0, 1}∗ : w has a 1 in the third position from the right}. The following state diagram defines an NFA that accepts all strings that are in A, and rejects all strings that are not in A. 0, 1 1 0, 1 0, 1 q1 q2 q3 q4 38 Chapter 2. Finite Automata and Regular Languages This NFA does the following. If it is in the start state q1 and reads the symbol 1, then it either stays in state q1 or it “guesses” that this symbol is the third symbol from the right in the input string. In the latter case, the NFA switches to state q2 , and then it “verifies” that there are indeed exactly two remaining symbols in the input string. If there are more than two remaining symbols, then the NFA hangs (in state q4 ) after having read the next two symbols. Observe how this guessing mechanism is used: The automaton can only read the input string once, from left to right. Hence, it does not know when it reaches the third symbol from the right. When the NFA reads a 1, it can guess that this is the third symbol from the right; after having made this guess, it verifies whether or not the guess was correct. In Section 2.2.3, we have seen a DFA for the same language A. Observe that the NFA has a much simpler structure than the DFA. 2.4.3 A third example Consider the following state diagram, which defines an NFA whose alphabet is {0}. 0 ε 0 ε 0 0 0 This NFA accepts the language A = {0k : k ≡ 0 mod 2 or k ≡ 0 mod 3}, where 0k is the string consisting of k many 0s. (If k = 0, then 0k = .) Observe that A is the union of the two languages A1 = {0k : k ≡ 0 mod 2} 2.4. Nondeterministic finite automata 39 and A2 = {0k : k ≡ 0 mod 3}. The NFA basically consists of two DFAs: one of these accepts A1 , whereas the other accepts A2. Given an input string w, the NFA has to decide whether or not w ∈ A, which is equivalent to deciding whether or not w ∈ A1 or w ∈ A2. The NFA makes this decision in the following way: At the start, it “guesses” whether (i) it is going to check whether or not w ∈ A1 (i.e., the length of w is even), or (ii) it is going to check whether or not w ∈ A2 (i.e., the length of w is a multiple of 3). After having made the guess, it verifies whether or not the guess was correct. If w ∈ A, then there exists a way of making the correct guess and verifying that w is indeed an element of A (by ending in an accept state). If w 6∈ A, then no matter which guess is made, the NFA will never end in an accept state. 2.4.4 Definition of nondeterministic finite automaton The previous examples give you an idea what nondeterministic finite au- tomata are and how they work. In this section, we give a formal definition of these automata. For any alphabet Σ, we define Σ to be the set Σ = Σ ∪ {}. Recall the notion of a power set: For any set Q, the power set of Q, denoted by P(Q), is the set of all subsets of Q, i.e., P(Q) = {R : R ⊆ Q}. Definition 2.4.1 A nondeterministic finite automaton (NFA) is a 5-tuple M = (Q, Σ, δ, q, F ), where 1. Q is a finite set, whose elements are called states, 2. Σ is a finite set, called the alphabet; the elements of Σ are called symbols, 3. δ : Q × Σ → P(Q) is a function, called the transition function, 4. q is an element of Q; it is called the start state, 5. F is a subset of Q; the elements of F are called accept states. 40 Chapter 2. Finite Automata and Regular Languages As for DFAs, the transition function δ can be thought of as the “program” of the finite automaton M = (Q, Σ, δ, q, F ): Let r ∈ Q, and let a ∈ Σ. Then δ(r, a) is a (possibly empty) subset of Q. If the NFA M is in state r, and if it reads a (where a may be the empty string ), then M can switch from state r to any state in δ(r, a). If δ(r, a) = ∅, then M cannot continue and the computation hangs. The example given in Section 2.4.1 is an NFA, where Q = {q1 , q2 , q3 , q4 }, Σ = {0, 1}, the start state is q1 , the set of accept states is F = {q4 }, and the transition function δ is given by the following table: 0 1  q1 {q1 } {q1 , q2 } ∅ q2 {q3 } ∅ {q3 } q3 ∅ {q4 } ∅ q4 {q4 } {q4 } ∅ Definition 2.4.2 Let M = (Q, Σ, δ, q, F ) be an NFA, and let w ∈ Σ∗. We say that M accepts w, if1 w =  and the start state q is an accept state, or there exists an integer m ≥ 1, such that w can be written as w = y1 y2... ym , where yi ∈ Σ for all i with 1 ≤ i ≤ m, and there exists a sequence r0 , r1 ,... , rm of states in Q, such that – r0 = q, – ri+1 ∈ δ(ri , yi+1 ), for i = 0, 1,... , m − 1, and – rm ∈ F. Otherwise, we say that M rejects the string w. The NFA in the example in Section 2.4.1 accepts the string 01100. This can be seen by taking m = 6, 1 Thanks to Antoine Vigneron for pointing out an error in a previous version of this definition. 2.5. Equivalence of DFAs and NFAs 41 w = 01100 = y1 y2 y3 y4 y5 y6 , and r0 = q1 , r1 = q1 , r2 = q2 , r3 = q3 , r4 = q4 , r5 = q4 , and r6 = q4. Definition 2.4.3 Let M = (Q, Σ, δ, q, F ) be an NFA. The language L(M ) accepted by M is defined as L(M ) = {w ∈ Σ∗ : M accepts w }. 2.5 Equivalence of DFAs and NFAs You may have the impression that nondeterministic finite automata are more powerful than deterministic finite automata. In this section, we will show that this is not the case. That is, we will prove that a language can be accepted by a DFA if and only if it can be accepted by an NFA. In order to prove this, we will show how to convert an arbitrary NFA to a DFA that accepts the same language. What about converting a DFA to an NFA? Well, there is (almost) nothing to do, because a DFA is also an NFA. This is not quite true, because the transition function of a DFA maps a state and a symbol to a state, whereas the transition function of an NFA maps a state and a symbol to a set of zero or more states. The formal conversion of a DFA to an NFA is done as follows: Let M = (Q, Σ, δ, q, F ) be a DFA. Recall that δ is a function δ : Q × Σ → Q. We define the function δ 0 : Q × Σ → P(Q) as follows. For any r ∈ Q and for any a ∈ Σ ,  0 {δ(r, a)} if a 6= , δ (r, a) = ∅ if a = . Then N = (Q, Σ, δ 0 , q, F ) is an NFA, whose behavior is exactly the same as that of the DFA M ; the easiest way to see this is by observing that the state diagrams of M and N are equal. Therefore, we have L(M ) = L(N ). In the rest of this section, we will show how to convert an NFA to a DFA: Theorem 2.5.1 Let N = (Q, Σ, δ, q, F ) be a nondeterministic finite automa- ton. There exists a deterministic finite automaton M , such that L(M ) = L(N ). 42 Chapter 2. Finite Automata and Regular Languages Proof. Recall that the NFA N can (in general) perform more than one computation on a given input string. The idea of the proof is to construct a DFA M that runs all these different computations simultaneously. (We have seen this idea already in the proof of Theorem 2.3.1.) To be more precise, the DFA M will have the following property: the state that M is in after having read an initial part of the input string corresponds exactly to the set of all states that N can reach after having read the same part of the input string. We start by presenting the conversion for the case when N does not contain -transitions. In other words, the state diagram of N does not contain any edge that has  as a label. (Later, we will extend the conversion to the general case.) Let the DFA M be defined as M = (Q0 , Σ, δ 0 , q 0 , F 0 ), where the set Q0 of states is equal to Q0 = P(Q); observe that |Q0 | = 2|Q| , the start state q 0 is equal to q 0 = {q}; so M has the “same” start state as N , the set F 0 of accept states is equal to the set of all elements R of Q0 having the property that R contains at least one accept state of N , i.e., F 0 = {R ∈ Q0 : R ∩ F 6= ∅}, the transition function δ 0 : Q0 × Σ → Q0 is defined as follows: For each R ∈ Q0 and for each a ∈ Σ, [ δ 0 (R, a) = δ(r, a). r∈R Let us see what the transition function δ 0 of M does. First observe that, since N is an NFA, δ(r, a) is a subset of Q. This implies that δ 0 (R, a) is the union of subsets of Q and, therefore, also a subset of Q. Hence, δ 0 (R, a) is an element of Q0. The set δ(r, a) is equal to the set of all states of the NFA N that can be reached from state r by reading the symbol a. We take the union of these sets δ(r, a), where r ranges over all elements of R, to obtain the new set δ 0 (R, a). This new set is the state that the DFA M reaches from state R, by reading the symbol a. 2.5. Equivalence of DFAs and NFAs 43 In this way, we obtain the correspondence that was given in the beginning of this proof. After this warming-up, we can consider the general case. In other words, from now on, we allow -transitions in the NFA N. The DFA M is defined as above, except that the start state q 0 and the transition function δ 0 have to be modified. Recall that a computation of the NFA N consists of the following: 1. Start in the start state q and make zero or more -transitions. 2. Read one “real” symbol of Σ and move to a new state (or stay in the current state). 3. Make zero or more -transitions. 4. Read one “real” symbol of Σ and move to a new state (or stay in the current state). 5. Make zero or more -transitions. 6. Etc. The DFA M will simulate this computation in the following way: Simulate 1. in one single step. As we will see below, this simulation is implicitly encoded in the definition of the start state q 0 of M. Simulate 2. and 3. in one single step. Simulate 4. and 5. in one single step. Etc. Thus, in one step, the DFA M simulates the reading of one “real” symbol of Σ, followed by making zero or more -transitions. To formalize this, we need the notion of -closure. For any state r of the NFA N , the -closure of r, denoted by C (r), is defined to be the set of all states of N that can be reached from r, by making zero or more -transitions. For any state R of the DFA M (hence, R ⊆ Q), we define [ C (R) = C (r). r∈R 44 Chapter 2. Finite Automata and Regular Languages How do we define the start state q 0 of the DFA M ? Before the NFA N reads its first “real” symbol of Σ, it makes zero or more -transitions. In other words, at the moment when N reads the first symbol of Σ, it can be in any state of C (q). Therefore, we define q 0 to be q 0 = C (q) = C ({q}). How do we define the transition function δ 0 of the DFA M ? Assume that M is in state R, and reads the symbol a. At this moment, the NFA N would have been in any state r of R. By reading the symbol a, N can switch to any state in δ(r, a), and then make zero or more -transitions. Hence, the NFA can switch to any state in the set C (δ(r, a)). Based on this, we define δ 0 (R, a) to be [ δ 0 (R, a) = C (δ(r, a)). r∈R To summarize, the NFA N = (Q, Σ, δ, q, F ) is converted to the DFA M = (Q0 , Σ, δ 0 , q 0 , F 0 ), where Q0 = P(Q), q 0 = C ({q}), F 0 = {R ∈ Q0 : R ∩ F 6= ∅}, δ 0 : Q0 × Σ → Q0 is defined as follows: For each R ∈ Q0 and for each a ∈ Σ, [ δ 0 (R, a) = C (δ(r, a)). r∈R The results proved until now can be summarized in the following theorem. Theorem 2.5.2 Let A be a language. Then A is regular if and only if there exists a nondeterministic finite automaton that accepts A. 2.5.1 An example Consider the NFA N = (Q, Σ, δ, q, F ), where Q = {1, 2, 3}, Σ = {a, b}, q = 1, F = {2}, and δ is given by the following table: 2.5. Equivalence of DFAs and NFAs 45 a b  1 {3} ∅ {2} 2 {1} ∅ ∅ 3 {2} {2, 3} ∅ The state diagram of N is as follows: ǫ 1 2 a a a, b 3 b We will show how to convert this NFA N to a DFA M that accepts the same language. Following the proof of Theorem 2.5.1, the DFA M is specified by M = (Q0 , Σ, δ 0 , q 0 , F 0 ), where each of the components is defined below. Q0 = P(Q). Hence, Q0 = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. q 0 = C ({q}). Hence, the start state q 0 of M is the set of all states of N that can be reached from N ’s start state q = 1, by making zero or more -transitions. We obtain q 0 = C ({q}) = C ({1}) = {1, 2}. F 0 = {R ∈ Q0 : R ∩ F 6= ∅}. Hence, the accept states of M are those states that contain the accept state 2 of N. We obtain F 0 = {{2}, {1, 2}, {2, 3}, {1, 2, 3}}. 46 Chapter 2. Finite Automata and Regular Languages δ 0 : Q0 × Σ → Q0 is defined as follows: For each R ∈ Q0 and for each a ∈ Σ, [ δ 0 (R, a) = C (δ(r, a)). r∈R In this example δ 0 is given by δ 0 (∅, a) = ∅ δ 0 (∅, b) = ∅ δ 0 ({1}, a) = {3} δ 0 ({1}, b) = ∅ δ 0 ({2}, a) = {1, 2} δ 0 ({2}, b) = ∅ δ 0 ({3}, a) = {2} δ 0 ({3}, b) = {2, 3} δ 0 ({1, 2}, a) = {1, 2, 3} δ 0 ({1, 2}, b) = ∅ δ 0 ({1, 3}, a) = {2, 3} δ 0 ({1, 3}, b) = {2, 3} δ 0 ({2, 3}, a) = {1, 2} δ 0 ({2, 3}, b) = {2, 3} δ 0 ({1, 2, 3}, a) = {1, 2, 3} δ 0 ({1, 2, 3}, b) = {2, 3} The state diagram of the DFA M is as follows: 2.5. Equivalence of DFAs and NFAs 47 a, b b 0/ {1} b b {2} a a a {1, 2} {3} b a a a, b {1, 3} {2, 3} b b {1, 2, 3} a We make the following observations: The states {1} and {1, 3} do not have incoming edges. Therefore, these two states cannot be reached from the start state {1, 2}. The state {3} has only one incoming edge; it comes from the state {1}. Since {1} cannot be reached from the start state, {3} cannot be reached from the start state. The state {2} has only one incoming edge; it comes from the state {3}. Since {3} cannot be reached from the start state, {2} cannot be reached from the start state. Hence, we can remove the four states {1}, {2}, {3}, and {1, 3}. The resulting DFA accepts the same language as the DFA above. This leads to the following state diagram, which depicts a DFA that accepts the same language as the NFA N : 48 Chapter 2. Finite Automata and Regular Languages a, b 0/ b {1, 2} a a {2, 3} b b {1, 2, 3} a 2.6 Closure under the regular operations In Section 2.3, we have defined the regular operations union, concatenation, and star. We proved in Theorem 2.3.1 that the union of two regular lan- guages is a regular language. We also explained why it is not clear that the concatenation of two regular languages is regular, and that the star of a reg- ular language is regular. In this section, we will see that the concept of NFA, together with Theorem 2.5.2, can be used to give a simple proof of the fact that the regular languages are indeed closed under the regular operations. We start by giving an alternative proof of Theorem 2.3.1: Theorem 2.6.1 The set of regular languages is closed under the union op- eration, i.e., if A1 and A2 are regular languages over the same alphabet Σ, then A1 ∪ A2 is also a regular language. 2.6. Closure under the regular operations 49 q1 q1 ε M1 q0 ε q2 q2 M2 M Figure 2.1: The NFA M accepts L(M1 ) ∪ L(M2 ). Proof. Since A1 is regular, there is, by Theorem 2.5.2, an NFA M1 = (Q1 , Σ, δ1 , q1 , F1 ), such that A1 = L(M1 ). Similarly, there is an NFA M2 = (Q2 , Σ, δ2 , q2 , F2 ), such that A2 = L(M2 ). We may assume that Q1 ∩ Q2 = ∅, because otherwise, we can give new “names” to the states of Q1 and Q2. From these two NFAs, we will construct an NFA M = (Q, Σ, δ, q0 , F ), such that L(M ) = A1 ∪ A2. The construction is illustrated in Figure 2.1. The NFA M is defined as follows: 1. Q = {q0 } ∪ Q1 ∪ Q2 , where q0 is a new state. 2. q0 is the start state of M. 3. F = F1 ∪ F2. 4. δ : Q × Σ → P(Q) is defined as follows: For any r ∈ Q and for any 50 Chapter 2. Finite Automata and Regular Languages a ∈ Σ ,    δ1 (r, a) if r ∈ Q1 , δ2 (r, a) if r ∈ Q2 ,  δ(r, a) =   {q1 , q2 } if r = q0 and a = , ∅ if r 6 . = q0 and a =  Theorem 2.6.2 The set of regular languages is closed under the concatena- tion operation, i.e., if A1 and A2 are regular languages over the same alphabet Σ, then A1 A2 is also a regular language. Proof. Let M1 = (Q1 , Σ, δ1 , q1 , F1 ) be an NFA, such that A1 = L(M1 ). Similarly, let M2 = (Q2 , Σ, δ2 , q2 , F2 ) be an NFA, such that A2 = L(M2 ). As in the proof of Theorem 2.6.1, we may assume that Q1 ∩ Q2 = ∅. We will construct an NFA M = (Q, Σ, δ, q0 , F ), such that L(M ) = A1 A2. The construction is illustrated in Figure 2.2. The NFA M is defined as follows: 1. Q = Q1 ∪ Q2. 2. q0 = q1. 3. F = F2. 4. δ : Q × Σ → P(Q) is defined as follows: For any r ∈ Q and for any a ∈ Σ ,    δ1 (r, a) if r ∈ Q1 and r 6∈ F1 , δ1 (r, a) if r ∈ F1 and a 6= ,  δ(r, a) =   δ1 (r, a) ∪ {q2 } if r ∈ F1 and a = , δ2 (r, a) if r ∈ Q2.  Theorem 2.6.3 The set of regular languages is closed under the star oper- ation, i.e., if A is a regular language, then A∗ is also a regular language. 2.6. Closure under the regular operations 51 q1 q2 M1 M2 ε q0 q2 ε ε M Figure 2.2: The NFA M accepts L(M1 )L(M2 ). q1 ε q1 ε ε q0 ε N M Figure 2.3: The NFA M accepts (L(N ))∗. Proof. Let Σ be the alphabet of A and let N = (Q1 , Σ, δ1 , q1 , F1 ) be an NFA, such that A = L(N ). We will construct an NFA M = (Q, Σ, δ, q0 , F ), such that L(M ) = A∗. The construction is illustrated in Figure 2.3. The NFA M is defined as follows: 52 Chapter 2. Finite Automata and Regular Languages 1. Q = {q0 } ∪ Q1 , where q0 is a new state. 2. q0 is the start state of M. 3. F = {q0 } ∪ F1. (Since  ∈ A∗ , q0 has to be an accept state.) 4. δ : Q × Σ → P(Q) is defined as follows: For any r ∈ Q and for any a ∈ Σ ,    δ1 (r, a) if r ∈ Q1 and r 6∈ F1 ,  δ1 (r, a) if r ∈ F1 and a 6= ,