User:Whiteknight/Automata Theory

This page is an outline for a proposed book or project. This is only a planning page, not an actual book.

1. Do not add sub-pages to this outline.
2. Any user may edit this outline, but Whiteknight maintains complete editorial control on this page.
3. This page may be deleted without warning.

This outline was last edited on 2 November 2010. Last edit over 169 months ago. Please update.

(Whiteknight) (Discuss) (Book Foundry) (Current Books) (VBD Edit)

This outline will serve to fill a hole in available material here on wikibooks. I would like this book to be a precursor to the Cellular Automata book, and as the necessary companion material to other books on periphery topics such as Compiler construction, etc. Also, this would serve as a good theoretical basis for my future book on Lex and Yacc.

I intend to shelve this book on the mathematics bookshelf, even though I am well aware that most of the uses of Automata theory will be found on the CS bookshelf.

Introduction

This book is going to consider the topic of Automata Theory, Sequential Machines, and Artificial Languages. The goal of this book is to become a solid foundational work for topics that are based off the automata theory framework.

Table of Contents

• Abstract Algebra
  • Basic introduction
  • Development of key terms and notation
  • Redirection to Abstract algebra
• Sequential Machines
  • What are Sequential Machines
  • Mealy Machines
  • Moore Machines
  • Machine Equivalence
  • Incompletely specified machines
• Decomposition of Machines
  • Interconnection of Sequential Machines
  • Composite Machines
  • Partitioning
  • Covering
• Measurement and Control
  • Terminal State identification
  • Finite Memory Machines
  • Initial State Identification
  • Information-lossless Machines
  • Machine Identification
  • Redirect to Control Systems
• Regular Expressions
  • Relationships between input and machine state
  • Regular Expressions Introduction
  • Regular Expressions and state diagrams
  • Redirection to Regular Expressions
• Vectors and Linear Transforms
  • Vector Spaces
  • Linear Transforms
  • Canonical Representation
  • Invariant Factors
  • Redirect to Linear algebra
• Linear Sequential Machines
  • Representing Linear Machines
  • Equivalent Linear Machines
  • Autonomous Response
  • Sequential Networks
  • Transfer Functions
• Turing Machines
  • Turing Machines Introduction
  • Programing turing Machines
  • Recursive Functions
  • Predicates
  • Computability
  • Enumerable Sets
• Artificial Languages
  • Languages
  • Phase-Structure Grammars
  • Language Operations
  • Decision Problems
  • Redirect to Compiler construction

Resources

• Abstract algebra
• Compiler construction
• Cellular Automata
• Regular Expressions
• Linear algebra
• Control Systems
• Self-Replicating Automata
• Computer Science:Programming Languages

Original outline based off the following book:

• Booth, Taylor L. "Sequential Machines and Automata Theory", John Wiley and Sons, New York, 1967.

Visual Book Designer Outline

This outline is a saved state for use with Whiteknight's Visual Book Designer gadget. Do not edit the outline on this page directly unless you understand the syntax. Improper editing here could make it impossible to load this outline into the gadget again.
Edit This Outline In The Gadget

Automata Theory =Abstract Algebra

• Abstract Algebra Introduction
• Terms and Notations

=Sequential Machines

• Sequential Machines Introduction
• Mealy Machines
• Moore Machines
• Machine Equivalence
• Incompletely Specified Machines

=Decomposition of Machines

• Interconnection of Sequential Machines
• Composite Machines
• Partitioning
• Covering

=Measurement and Control

• Terminal State Identification
• Finite Memory Machines
• Initial State Identification
• Information-Lossless Machines
• Machine Identfication

=Regular Expressions

• Regular Expression Introduction
• Relationships Between Input and State
• Regular Expression State Diagrams

=Vectors and Linear Transforms

• Vector Spaces
• Linear Transforms
• Canonical Representation
• Invariant Factors

=Linear Sequential Machines

• Representing Linear Machines
• Equivalent Linear Machines
• Autonomous Response
• Sequential Networks
• Transfer Functions

=Turing Machines

• Turing Machines Introduction
• Programming Turing Machines
• Recursive Functions
• Predicates
• Computability
• Enumerable Sets

=Artificial Languages

• Languages Introduction
• Phase-Structure Grammars
• Language Operations
• Decision Problems

End of outline. Below this point is normal text and can be edited like normal.