# 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.

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

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

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[edit]

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[edit]

- 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[edit]

- 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

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