This book covers various topics on Automata, Formal Languages, Computablity, etc and more. Following are the few topics explained in this theory of computation book.
- Automata Notation, Proofs
- Set Theory
- The Natural numbers and Induction
- Foundations of Language Theory
- Operations on Languages
- Deterministic Finite Automata
- The Cross Product Construction
- Non-Deterministic Finite Automata
- Directed Graphs and Paths
- Labeled Graphs and Automata
- The Theorem of Myhill and Nerode
- Minimal DFAs
- State Equivalence and Minimal DFA’s
- Formal Languages
- A Grammar for Parsing English
- Context-Free Grammars
- Derivations and Context-Free Languages
- Normal Forms for Context-Free Grammars, Chomsky Normal Form
- Regular Languages are Context-Free
- Useless Productions in Context-Free Grammars
- The Greibach Normal Form
- Least Fixed-Points
- Context-Free Languages as Least Fixed-Points
- Least Fixed-Points and the Greibach Normal Form
- Tree Domains and Gorn Trees
- Derivations Trees
- Ogden’s Lemma
- Pushdown Automata
- From Context-Free Grammars To PDA’s
- From PDA’s To Context-Free Grammars
- Computability
- Computations of Turing Machines
- The Primitive Recursive Functions
- The Partial Recursive Functions
- Recursively Enumerable Languages and Recursive Languages
- Phrase-Structure Grammars
- Derivations and Type-0 Languages
- Type-0 Grammars and Context-Sensitive Grammars
- The Halting Problem
- A Univeral Machine
- The Parameter Theorem
- Recursively Enumerable Languages
- Hilbert’s Tenth Problem
- DNA Computing
- Analog Computing
- Scientific Computing/Dynamical Systems
- Quantum Computing
