Overview Page

Web Readings

• Informal Properties of an Algorithm
• Formal Definitions of Finite State Machines
• Three Ways of Viewing a Finite State Machine
  • Finite State Machine Assignment
• Introductory Chapter on Machines and Computation
• Turing on Turing Machines
• Turing Machine Examples
  • Some "Apple" Acceptors
  • AnBn Turing Machine
  • AnBnCn Turing Machine
    • Turing Machine Assignment
  • Encoding of Turing Machines and the Universal Turing Machine
• Hierarchy of Grammars Defined
  • Some Examples of the Different Types of Grammars
  • Derivation Example
• Formal Theory Essay Question
• More Advanced Material
  • Learning Issues in the Context of FSM
    • "Learning" and "FSM"
    • Finding the Minimal FSM
  • FSM and Regular Expressions
  • Computational Complexity

Text Readings

Assignments

• Finite State Machine Assignment
• Turing Machine Assignment
• Formal Theory Essay Question