Transcription of Theory of Computation
1 Introduction to Theory of ComputationAnil Maheshwari Michiel SmidSchool of Computer ScienceCarleton 17, 2019iiContentsContentsPrefacevi1 Purpose and motivation .. Complexity Theory .. Computability Theory .. automata Theory .. This course .. Mathematical preliminaries .. Proof techniques .. Direct proofs .. Constructive proofs .. Nonconstructive proofs .. Proofs by contradiction .. The pigeon hole principle .. Proofs by induction .. More examples of proofs .. 15 Exercises .. 182 Finite automata and Regular An example: Controling a toll gate .. Deterministic finite automata .. A first example of a finite automaton .. A second example of a finite automaton.
2 A third example of a finite automaton .. Regular operations .. Nondeterministic finite automata .. A first example .. A second example .. A third example .. Definition of nondeterministic finite automaton .. Equivalence of DFAs and NFAs .. An example .. Closure under the regular operations .. Regular expressions .. Equivalence of regular expressions and regular languages .. Every regular expression describes a regular language . Converting a DFA to a regular expression .. The pumping lemma and nonregular languages .. Applications of the pumping lemma .. Higman s Theorem .. Dickson s Theorem .. Proof of Higman s Theorem .. 77 Exercises .. 803 Context-Free Context-free grammars.
3 Examples of context-free grammars .. Properly nested parentheses .. A context-free grammar for a nonregular language .. A context-free grammar for the complement of a non-regular language .. A context-free grammar that verifies addition .. Regular languages are context-free .. An example .. Chomsky normal form .. An example .. Pushdown automata .. Examples of pushdown automata .. Properly nested parentheses .. Strings of the form 0n1n.. Strings withbin the middle .. Equivalence of pushdown automata and context-free grammars The pumping lemma for context-free languages .. Proof of the pumping lemma .. Applications of the pumping lemma .. 128 ContentsvExercises .. 1324 Turing Machines and the Church-Turing Definition of a Turing machine.
4 Examples of Turing machines .. Accepting palindromes using one tape .. Accepting palindromes using two tapes .. Acceptinganbncnusing one tape .. Acceptinganbncnusing tape alphabet{a, b, c, }.. Acceptingambncmnusing one tape .. Multi-tape Turing machines .. The Church-Turing Thesis .. 151 Exercises .. 1525 Decidable and Undecidable Decidability .. The languageADFA.. The languageANFA.. The languageACFG.. The languageATM.. The Halting Problem .. Countable sets .. The Halting Problem revisited .. Rice s Theorem .. Proof of Rice s Theorem .. Enumerability .. Hilbert s problem .. The languageATM.. Where does the term enumerable come from? .. Most languages are not enumerable.
5 The set of enumerable languages is countable .. The set of all languages is not countable .. There are languages that are not enumerable .. The relationship between decidable and enumerable languages A languageAsuch that bothAandAare not enumerable .. not enumerable .. not enumerable .. 188 Exercises .. 189viContents6 Complexity The running time of algorithms .. The complexity classP.. Some examples .. The complexity classNP.. contained inNP.. DecidingNP-languages in exponential time .. Summary .. Non-deterministic algorithms .. languages .. Two examples of reductions .. Definition of NP-completeness .. AnNP-complete domino game .. Examples ofNP-complete languages .. 231 Exercises.
6 2357 Summary239 PrefaceThis is a free textbook for an undergraduate course on the Theory of Com-putation, which we have been teaching at Carleton University since the 2011/2012 academic year, this course was offered as a second-yearcourse (COMP 2805) and was compulsory for all Computer Science with the 2012/2013 academic year, the course has been downgradedto a third-year optional course (COMP 3803).We have been developing this book since we started teaching this , we cover most of the material from Chapters 2 5 during a 12-weekterm with three hours of classes per material from Chapter 6, on Complexity Theory , is taught in thethird-year course COMP 3804 (Design and Analysis of Algorithms). In theearly years of COMP 2805, we gave a two-lecture overview of ComplexityTheory at the end of the term.
7 Even though this overview has disappearedfrom the course, we decided to keep Chapter 6. This chapter has not beenrevised/modified for a long course as we teach it today has been influenced by the following twotextbooks: Introduction to the Theory of Computation (second edition), by MichaelSipser, Thomson Course Technnology, Boston, 2006. Einf uhrung in die Theoretische Informatik, by Klaus Wagner, Springer-Verlag, Berlin, reading this text, we recommend that you also take a look atthese excellent textbooks, as well as one or more of the following ones: Elements of the Theory of Computation (second edition), by HarryLewis and Christos Papadimitriou, Prentice-Hall, Introduction to Languages and the Theory of Computation (thirdedi-tion), by John Martin, McGraw-Hill, 2003.
8 Introduction to automata Theory , Languages, and Computation (thirdedition), by John Hopcroft, Rajeev Motwani, Jeffrey Ullman, AddisonWesley, 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 Purpose and motivationThis course is on theTheory of Computation , which tries to answer thefollowing questions: What are the mathematical properties of computer hardware andsoft-ware? What is acomputationand what is analgorithm? Can we give rigorousmathematical definitions of these notions? What are thelimitationsof 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 field of research was started by mathematicians and logicians in the1930 s, when they were trying to understand the meaning of a Computation .
9 A central question asked was whether all mathematical problems can besolved in a systematic way. The research that started in those days led tocomputers as we know them , the Theory of Computation can be divided into the follow-ing three areas: Complexity Theory , Computability Theory , and 1. Complexity theoryThe main question asked in this area is What makes some problems com-putationallyhardand other problemseasy? 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 thefastest way to drive from Ottawa to Miami. On the other hand, a problem iscalled hard , if it cannot be solved efficiently, or if we don t know whetherit can be solved efficiently.
10 Examples of hard problems are (i) time tablescheduling for all courses at Carleton, (ii) factoring a 300-digit integer intoits prime factors, and (iii) computing a layout for chips in Question in Complexity Theory :Classify problems ac-cording to their degree of difficulty . Give a rigorous proof thatproblems that seem to be hard are really hard . Computability theoryIn the 1930 s, G odel, Turing, and Church discovered that some ofthe fun-damental mathematical problems cannot be solved by a computer . (Thismay sound strange, because computers were invented only in the 1940 s).An example of such a problem is Is an arbitrary mathematical statementtrue or false? To attack such a problem, we need formal definitions of thenotions of computer, algorithm, and theoretical models that were proposed in order to understand solvableand unsolvable problems led to the development of real Question in Computability Theory :Classify problemsas being solvable or Purpose and automata theoryAutomata Theory deals with definitions and properties of different types of Computation models.
