1. Languages 1
1.1. Symbol 2
1.2. Alphabet 2
1.3. Word 3
1.3.1. Basic operations on words 3
1.4. Languages 8
1.4.1. Operations on languages 9
1.5. Three fundamental questions 12
Exercises with solutions 13
2. Formal Grammars 17
2.1. Introduction 18
2.2. Formal Grammar 19
2.3. Derivation 22
2.4. Language generated by a grammar 24
2.4.1. Equivalence of two grammars 25
2.5. The Chomsky Hierarchy 26
2.5.1. General Grammar 26
2.5.2. Type 1 Grammar 27
2.5.3. Context-free grammar 29
2.5.4. Regular Grammar 30
2.5.5. The empty word 31
2.6. Concept of automaton 32
Exercises and solutions 35
3. Regular Languages 39
3.1. Regular Grammars 41
3.2. Finite automata 42
3.2.1. Deterministic finite automata 43
3.2.1.1. Configuration and derivation 45
3.2.1.2. Acceptance of a language by finite automata 47
3.2.1.3. Representations of a finite automaton 49
3.2.1.4. Equivalent automata and Complete automata 51
3.2.2. Non-deterministic finite automata 55
3.2.3. Conversion of a NDFA to a DFA 58
3.2.3.1. Elimination of ε-transitions 63
3.2.4. Minimisation of finite automata 66
3.2.4.1. Indistinguishability 67
3.2.4.2. Nerode congruence 69
3.2.4.3. Equivalence class 70
3.2.4.4. Quotient automaton 71
3.2.4.5. Congruence for words 71
3.2.4.6. Moore Algorithm 72
3.3. Finite automata and regular grammars 76
3.3.1. Regular grammar from finite automaton 77
3.3.2. Finite automaton from regular grammar 78
3.4. Properties of regular languages 79
3.4.1. Ensemblistic properties 80
3.4.2. Pumping Lemma for regular languages 89
3.4.3. Decision problems 92
3.5. Regular expressions 94
3.5.1. Definitions 94
3.5.2. Algebraic properties 96
3.6. Finite automata and regular expressions 97
3.6.1. Finite automaton from a regular expression 97
3.6.2. Regular expression from a finite automaton 103
3.6.2.1. Brzozowsky and McCluskey method 103
3.6.2.2. Equation Method 107
Exercises with solutions 115
Programming project in C language
4. Context-free Languages 121
4.1. Context-free grammars 123
4.1.1. Derivations 125
4.1.2. Derivation tree 127
4.1.3. Ambiguity 129
4.2. Properties of context-free languages 138
4.2.1. Set properties 138
4.2.2. Pumping Lemma 140
4.2.3. Decision problems 141
4.3. Transforming context-free grammars 142
4.3.1. Reduced grammars 142
4.3.1.1. Removal of non-productive symbols 143
4.3.1.2. Removal of unreachable symbols 145
4.3.2. Proper grammars 147
4.3.2.1. Removal of ε-rules 148
4.3.2.2. Removal of unit rules 151
4.3.3. Left recursive grammars 153
4.3.4. Chomsky Normal Form 158
4.3.5. Greibach Normal Form 161
4.4. Pushdown automata 163
4.4.1. Configuration and computation 166
4.4.2. Acceptance of a language 169
4.4.3. Determinism vs non-determinism 172
4.5. Pushdown automata and context-free grammars 176
4.5.1. PDA from a CFG 176
Exercises with solutions 179
5. Recursively Enumerable Languages 183
5.1. General Grammars 185
5.2. Turing Machine 188
5.2.1. Configuration and computation 191
5.2.2. Acceptance 194
5.3. Recursively enumerable languages 196
5.3.1. Recursive languages 197
5.3.2. Recursively enumerable languages 198
5.3.3. Discussion 199
5.4. Determinism vs non-determinism 199
5.5. Turing machine as a calculator 199
Exercises with solutions 201
Appendix 205
A. Solutions to the exercises 207
A.1. Chapter 1 solutions 207
A.2. Chapter 2 solutions 210
A.3. Chapter 3 solutions 214
A.4. Chapter 4 solutions 224
A.5. Chapter 5 solutions 233
B. Final exams 238
B.1. Exam 1 238
B.2. Exam 2 240
B.3. Exam 3 242
B.4. Exam 4 244
B.5. Exam 5 245
C. Final exam corrections 247
C.1. Exam 1 correction 247
C.2. Exam 2 correction 251
C.3. Exam 3 correction 255
C.4. Exam 4 correction 257
C.5. Exam 5 correction 260
D. Supplementary exercises (no answers) 263
D.1. Chapter 1 263
D.2. Chapter 2 265
D.3. Chapter 3 267
D.4. Chapter 4 272
D.5. Chapter 5 279
Bibliography 281
Index
