User:Whiteknight/Automata Theory
- 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 169 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 | edit source]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 | edit source]- 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 | edit source]- 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