Introduction to the Theory of Computation

1. finite automata

• Deterministic Finite Automata
• Non-Deterministic Finite Automata
• Finite Automata with Epsilon-Transitions
• Formal Notation for Epsilon-NFAs
• Epsilon-Closure
• Extended Transistions and Languages for Epsilon-NFAs
• Eliminating Epsilon-Transitions

2. regular expressions

• Finite Automata and Regular Expressions
• Algebraic Laws of Regular Expressions
• The Pumping Lemma
• Closure Properties of Regular Languages

3. Context-Free Grammars

• Definition
• Parse Trees
• Ambiguity in Grammars and Languages

4. Pushdown Automata

• Definition
• Languages of PDA

5. Context-Free Languages Equivalence of PDAs and CFGs

• Chomsky Normal Form for Context-Free Grammars
• Closure Properties of Context-Free Languages
• Decision Problems for CFLs

6. Turing Machines

• Definition
• Undecidability
• Undecidable Problems about Turing Machines
• Post's Correspondence Problem

7. Intractable Problems

• P and NP Classes
• The SAT problem
• Restricted SAT problems
• Independent Sets
• Directed Hamiltonian-Circuit
• Undirected Hamiltonian-Circuit
• Traveling Salesman Problem

support companion site

context-free grammars