17 avr 2019 · Introduction to Languages and the Theory of Computation (third edi- tion), by John Martin, McGraw-Hill, 2003 • Introduction to Automata Theory
17 avr 2019 · Introduction to Languages and the Theory of Computation (third edi- tion), by John Martin, McGraw-Hill, 2003 • Introduction to Automata Theory
of the correctness of various constructions concerning automata If presented clearly, these constructions convince and do not need further argument An in-
Remember finite automata and regular expressions Confronted with a problem that seems to re- quire more computer time than you can afford? Think back to
27 août 2019 · 2 Automata Theory Theoretical computer science is divided into three key areas: automata theory, computability theory, and complexity theory
Automata theory 5 1 Undecidable Problems from Language Theory puter science or engineering, and a course in theory is required-God knows
areas of automata theory, computability, and formal languages In various respects, this can be thought of as the elementary foundations of much of computer
1 Regular Languages 1 1 Finite Automata Formal definition of a finite automaton Examples of finite automata
25 sept 2014 · Introduction to Automata Theory, Languages, and Computation (third edition) Purpose of the Theory of Computation: Develop formal math-
turns out to be the crucial fact in proving many non-trivial things about finite state automata The formal mathematical statement of the pigeon hole principle is
automata, computability, and complexity These areas are linked by the question: What are the fundamental capabilities and limitations of computers?
[PDF] theory of quadratic equation
[PDF] theory of semiotics ferdinand de saussure pdf
[PDF] therapeutic drug monitoring pdf
[PDF] therapeutic drug monitoring ppt
[PDF] therapeutic drug monitoring principles
[PDF] therapeutic drug monitoring review
[PDF] thermal model of a house
[PDF] thermostat simulink
[PDF] thesis about british and american english
[PDF] thesis on android application development
[PDF] thesis outline example
[PDF] thirty years war essay question
[PDF] thirty years war essay thesis
[PDF] thirty years war political causes
[PDF] thirty years' war
Introduction to Theory of Computation Anil Maheshwari Michiel Smid School of Computer Science Carleton University Ottawa Canada {anil,michiel}@scs.carleton.ca
April 17, 2019 iiContents
ContentsPrefacevi 1 Introduction1 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 ivContents
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 . . . 56 2.8.1 Every regular expression describes a regular language . 57 2.8.2 Converting a DFA to a regular expression . . . . . . . 60 2.9 The pumping lemma and nonregular languages . . . . . . . . . 67 2.9.1 Applications of the pumping lemma . . . . . . . . . . . 69 2.10 Higman"s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 76 2.10.1 Dickson"s Theorem . . . . . . . . . . . . . . . . . . . . 76 2.10.2 Proof of Higman"s Theorem . . . . . . . . . . . . . . . 77 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3 Context-Free Languages91 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 0 n1n. . . . . . . . . . . . . . . . . 117
3.6.3 Strings withbin 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 Contentsv 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 Acceptinganbncnusing one tape . . . . . . . . . . . . . 143 4.2.4 Acceptinganbncnusing tape alphabet{a,b,c,?}. . . . 145 4.2.5 Acceptingambncmnusing 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 languageADFA. . . . . . . . . . . . . . . . . . . . 158 5.1.2 The languageANFA. . . . . . . . . . . . . . . . . . . . 159 5.1.3 The languageACFG. . . . . . . . . . . . . . . . . . . . 160 5.1.4 The languageATM. . . . . . . . . . . . . . . . . . . . 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 languageATM. . . . . . . . . . . . . . . . . . . . 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 languageAsuch that bothAand Aare not enumerable . . 186 5.8.1EQTMis not enumerable . . . . . . . . . . . . . . . . . 186 5.8.2 EQTMis not enumerable . . . . . . . . . . . . . . . . . 188 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 viContents
6 Complexity Theory197 quotesdbs_dbs2.pdfusesText_3
[PDF] Introduction to Theory of Computation - Computational Geometry Lab![[PDF] Introduction to Theory of Computation - Computational Geometry Lab](https://pdfprof.com/Listes/27/34799-27TheoryOfComputation.pdf.pdf.jpg "[PDF] Introduction to Theory of Computation - Computational Geometry Lab")