[PDF] Introduction to Theory of Computation

View - Download Introduction to Theory of Computation

Previous PDF

Next PDF

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] 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