دانلود کتاب Express Learning: Automata Theory and Formal Languages

فهرست مطالب :

Cover......Page 1
About the Author......Page 7
Contents......Page 8
Foreword......Page 12
Preface......Page 14
Acknowledgements......Page 16
1.1 Basics of Automata......Page 18
1.2 Finite State Machine......Page 19
1.3 State Equivalence and Minimization of Machine......Page 35
1.4 Incompletely Specified Machine and Minimal Machine......Page 40
1.5 Merger Graph and Compatibility Graph......Page 43
1.6 Finite Memory and Definite Memory Machine......Page 55
1.7 Information Lossless Machine and Inverse Machine......Page 69
1.8 Inverse Machine......Page 77
What We Have Learned So Far......Page 80
Solved Problems......Page 81
Multiple Choice Questions......Page 109
Exercises......Page 110
Fill in the Blanks......Page 115
Answers......Page 116
2.1 Basic Terminology and Definitions......Page 117
2.2 Grammar and Language......Page 118
2.3 Chomsky Hierarchy......Page 119
2.4 Examples......Page 121
2.5 Context-sensitive Grammar......Page 129
Solved Problems......Page 130
Multiple Choice Questions......Page 131
Exercises......Page 132
Fill in the Blanks......Page 133
Answers......Page 134
3.1 Basics About Finite Automata......Page 135
3.2 Transitional System......Page 138
3.3 Deterministic Finite Automata and Non-DeterministicFinite Automata......Page 140
3.4 NFA with Null Move......Page 145
3.5 Dead State......Page 150
3.6 Finite Automata with Output......Page 151
3.7 Conversion of Moore To Mealy Machine by Tabular Format......Page 155
3.8 Conversion of Mealy to Moore Machine by Tabular Format......Page 157
3.9 Conversion of Moore to Mealy Machine by Transitional Format......Page 161
3.10 Conversion of Mealy to Moore Machine by Transitional Format......Page 164
3.11 Minimization of Finite Automata......Page 168
3.12 Myhill-Nerode Theorem......Page 172
What We Have Learned So Far......Page 178
Solved Problems......Page 179
Multiple Choice Questions......Page 193
Exercises......Page 194
Fill in the Blanks......Page 197
Answers......Page 198
4.1 Basics of Regular Expression......Page 199
4.2 Arden Theorem......Page 203
4.3 Construction of Finite Automata Equivalent to a Regular Expression......Page 208
4.4 NFA With Є Move and Conversion to DFA By Є – Closure Method......Page 213
4.5 Equivalence of Two Finite Automata and Two Regular Expressions......Page 219
4.6 Construction of Regular Grammar from a Regular Expression......Page 222
4.7 Pumping Lemma and its Application......Page 225
4.8 Closure Properties of Regular Set......Page 231
Solved Problems......Page 235
Multiple Choice Questions......Page 244
Exercises......Page 245
Fill in the Blanks......Page 247
Answers......Page 248
5.1 Context Free Grammar: Definition and Examples......Page 249
5.2 Derivation and Parse Tree......Page 252
5.3 Ambiguity......Page 256
5.4 Left Recursion and Left Factoring......Page 260
5.5 Simplification of CFG......Page 263
5.6 Normal Form......Page 271
5.7 Constructing FA from Regular Grammar......Page 279
5.8 Closure Properties of CFL......Page 281
5.9 Pumping Lemma for CFL......Page 282
5.11 Decision Algorithms......Page 286
What We Have Learned So Far......Page 288
Solved Problems......Page 289
Multiple Choice Questions......Page 302
Exercises......Page 303
Fill in the Blanks......Page 305
Answer......Page 307
6.1 Basics of Pushdown Automata......Page 308
6.2 Acceptance by a PDA......Page 310
6.3 Examples......Page 311
6.4 Deterministic PDA and Non-Deterministic PDA......Page 325
6.5 Pushdown Automata from Context Free Grammar......Page 328
6.6 Graphical Notation for PDA......Page 333
What We Have Learned So Far......Page 334
Solved Problems......Page 335
Multiple Choice Questions......Page 345
Exercises......Page 346
Answers......Page 347
7.1 Basic of Turing Machine......Page 348
7.2 Examples......Page 350
7.3 Transitional Representation of Turing Machine......Page 363
What We Have Learned so Far......Page 364
Solved Problems......Page 365
Multiple Choice Questions......Page 369
Fill in the Blanks......Page 370
Answers......Page 371
References......Page 372
Index......Page 374