Formal Languages and Automata Theory
ISBN: 9788126520107
252 pages
eBook also available for institutional users
Description
Formal Languages and Automata theory presents the theoretical aspects of computer science, and helps define infinite languages in finite ways; construct algorithms for related problems and decide whether a string is in language or not. These are of practical importance in construction of compilers and designing of programming languages, thus establishing the course as a core paper in third/fourth year of various universities. This book adopts a holistic approach to learning from fundamentals of formal languages to undecidability problems. Its organization follows the order in which the course is taught over the years, and is well-accepted by the student community. The contents of each topic motivate the reader to easily understand the concepts rather than remember and reproduce.
1 Mathematical Preliminaries for Finite Automata and Formal Languages
1.1 Sets
1.2 Relations and Functions
1.3 Graphs and Trees
1.4 Mathematical Induction
1.5 Mathematical Logic
1.6 Formal Language
1.7 Chomsky Hierarchy Languages (CHL)
1.8 Automata Theory
1.9 Applications of Automata
2 Regular Expressions and Regular Languages
2.1 Regular Expressions
2.2 Regular Languages and Regular Grammar
2.3 Applications of REs
3 Finite State Automata
3.1 Deterministic Finite Automata
3.2 Non-Deterministic Finite Automata
3.3 NFA and Regular Expressions
3.4 Conversion of Finite Automata to Regular Expression
3.5 Conversion of NFA to DFA
3.6 NFA with e-Transitions (e-NFA)
3.7 Conversion from e-NFA to NFA
3.8 Conversion from e-NFA to DFA
3.9 Output Associated with Finite Automata
3.10 Moore and Mealy Machines
3.11 Minimization of Automata
3.12 Applications of FA
4 Properties of Regular Languages
4.1 Pumping Lemma for Regular Languages
4.2 Closure Properties of Regular Languages
4.3 Decision Properties of Regular Languages
5 Context-Free Grammars and Languages
5.1 Definition of Context-Free Grammar
5.2 Leftmost and Rightmost Derivations
5.3 Derivation Tree
5.4 Ambiguity in Grammar
5.5 Parsing
5.6 Removal of Useless Symbols and Unit Productions
5.7 Removal of e-productions
5.8 Normal Forms for CFG Specification
6 Pushdown Automata
6.1 Definition of PDA
6.2 Non-deterministic PDA
6.3 Instantaneous Description of PDA
6.4 Graphical Notations for PDA
6.5 Languages of PDA
6.6 Equivalence of PDAS and CFGS
6.7 Deterministic PDA
7 Properties of Context-Free Languages
7.1 Pumping Lemma for CFLs
7.2 Applications of Pumping Lemma
7.3 Linear Context-Free Languages
7.4 Ogden’s Lemma and its Applications
7.5 Closure Properties of CFLS
7.7 Decision Properties of CFLs
8 Turing Machines
8.1 Problems that Computers Cannot Solve
8.2 Basic Model of the Turing Machine
8.3 Representation of a Turing Machine
8.4 Language of Turing Machine
8.5 Computable Languages and Functions
8.6 Programming Techniques of Turing Machine
8.7 Variations of Turing Machines
8.8 Universal Turing Machine
9 Undecidability
Learning Objectives
9.1 Computers and Turing Machine
9.2 Recursively Enumerable Languages
9.3 Halting Problem
9.4 Rice theorem
9.5 Post-Correspondence Problem
Summary
Key Terms
Exercises
Model Question Paper 1
Model Question Paper 2
Bibliography
Index