Foundations of Computing

Foreword

Preface

Introduction

1. Formal Languages
2. Finite State Machines
3. Exercises
4. Chapter Summary
5. Regular Languages

Finite Automata

1. Where Are We?
2. Chapter Objectives
3. Deterministic Finite Automata
4. Exercises
5. Non-Deterministic Finite Automata
6. Equivalence of NFAs and DFAs
7. NFAs and Complements
8. Exercises
9. Minimal Automata
10. Exercises
11. Machines with Output
12. Computer Arithmetic
13. Lexical Analysis
14. Minimal Mealy Machines
15. Exercises
16. Chapter Summary

Regular Expressions and Grammars

1. Where Are We?
2. Chapter Objectives
3. Regular Expressions
4. Exercises
5. Equivalence of Regular Expressions and Regular Languages
6. From Regular Expression to NFA
7. From NFA to Regular Expression
8. Exercises
9. Regular Grammars
10. Left-Linear Grammars
11. Exercises
12. Chapter Summary

Properties of Regular Languages

1. Where Are We?
2. Chapter Objectives
3. Closure Properties
4. Computing Set Operations
5. Exercises
6. Decision Algorithms
7. Exercises
8. Infinite Regular Languages and a “Pumping Theorem”
9. Exercises
10. Chapter Summary
11. Context-Free Languages

Pushdown Automata

1. Where Are We?
2. Chapter Objectives
3. Adding a Stack to Finite Automata
4. Exercises
5. Pushdown Automata and Determinism
6. Exercise
7. Chapter Summary

Context-Free Grammars

1. Where Are We?
2. Chapter Objectives
3. Context-Free Grammars and Derivations
4. Simplifying Grammars
5. Exercises
6. Derivation Trees and Ambiguous Grammars
7. Operator Precedence
8. Operator Associativity
9. Expression Trees
10. Exercises
11. Equivalence of PDAs and CFGs
12. From CFG to PDA
13. From PDA to CFG (Special Case)
14. From PDA to CFG (General Case)
15. Exercises
16. Chapter Summary

Properties of Context-Free Languages

1. Where Are We?
2. Chapter Objectives
3. Chomsky Normal Form
4. Removing Lambda
5. Removing Unit Productions
6. Chomsky Normal Form Rules
7. Exercises
8. Closure Properties
9. Closure Properties of DCFLs
10. Exercises
11. Decision Algorithms
12. Is a CFL Empty or Infinite?
13. Exercises
14. Infinite CFLs and Another Pumping Theorem
15. Exercises
16. Chapter Summary
17. Recursively Enumerable Languages

Turing Machines

1. Where Are We?
2. Chapter Objectives
3. Prelude
4. Queue Machines
5. Exercise
6. The Standard Turing Machine
7. Subroutines
8. Halting
9. Exercises
10. Programming Exercise
11. Variations on Turing Machines
12. The Universal Turing Machine
13. Non-Deterministic TM = Deterministic TM
14. Programming Exercise
15. Chapter Summary

The Landscape of Formal Languages

1. Where Are We?
2. Chapter Objectives
3. Recursively Enumerable Languages
4. A Non-Recursive, RE Language
5. Context-Sensitive Languages
6. Properties of Recursively Enumerable Languages
7. Exercises
8. Unrestricted Grammars
9. Context-Sensitive Grammars
10. Equivalence of Unrestricted Grammars and Turing Machines
11. Exercises
12. The Chomsky Hierarchy
13. Countable Sets
14. Uncountable Sets
15. Chapter Summary

Computability

1. Chapter Objectives
2. The Halting Problem
3. Reductions and Undecidability
4. Exercises
5. Chapter Summary

Glossary

Bibliography