Express Learning : Automata Theory and Formal Languages

Express Learning is a series of books designed as quick reference guides to important undergraduate computer courses. The organized and accessible format of these books allows students to learn important concepts in an easy-to-understand, question-and-answer format. These portable learning tools have been designed as one-stop references for students to understand and master the subjects by themselves. 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 Annotation The organized and accessible format of "Automata Theory and Formal Languages" allows students to learn important concepts in an easy-to-understand, question-and-answer format. This portable learning tool has been designed as one-stop references for students to understand and master the subjects by themselves