Download The Theory of Languages and Computation, This note covers the subsequent topics: Automata, Set Theory, The Natural numbers and Induction, Foundations of Language Theory, Operations on Languages, deterministic Finite Automata, Formal Languages, Computability, Computations of turing Machines, The Primitive recursive Functions, The Partial recursive Functions, dna Computing, Analog Computing and Scientific Computing.


1 Automata
1.1 Notation
1.2 Proofs
1.3 Set Theory
1.4 The Natural numbers and Induction
1.5 Foundations of Language Theory
1.6 Operations on Languages
1.7 Deterministic Finite Automata
1.8 The Cross Product Construction
1.9 Non-Deterministic Finite Automata
1.10 Directed Graphs and Paths
1.11 Labeled Graphs and Automata
1.12 The Theorem of Myhill and Nerode
1.13 Minimal DFAs
1.14 State Equivalence and Minimal DFA’s

2 Formal Languages
2.1 A Grammar for Parsing English
2.2 Context-Free Grammars
2.3 Derivations and Context-Free Languages
2.4 Normal Forms for Context-Free Grammars, Chomsky Normal Form
2.5 Regular Languages are Context-Free
2.6 Useless Productions in Context-Free Grammars
2.7 The Greibach Normal Form
2.8 Least Fixed-Points
2.9 Context-Free Languages as Least Fixed-Points
2.10 Least Fixed-Points and the Greibach Normal Form
2.11 Tree Domains and Gorn Trees
2.12 Derivations Trees
2.13 Ogden’s Lemma
2.14 Pushdown Automata
2.15 From Context-Free Grammars To PDA’s
2.16 From PDA’s To Context-Free Grammars

3 Computability
3.1 Computations of Turing Machines
3.2 The Primitive Recursive Functions
3.3 The Partial Recursive Functions
3.4 Recursively Enumerable Languages and Recursive Languages
3.5 Phrase-Structure Grammars
3.6 Derivations and Type-0 Languages
3.7 Type-0 Grammars and Context-Sensitive Grammars
3.8 The Halting Problem
3.9 A Univeral Machine
3.10 The Parameter Theorem
3.11 Recursively Enumerable Languages
3.12 Hilbert’s Tenth Problem

4 Current Topics
4.1 DNA Computing
4.2 Analog Computing
4.3 Scientific Computing/Dynamical Systems
4.4 Quantum Computing