Finite Automata

Finite Automata

by Mark V. Lawson
     
 

ISBN-10: 1584882557

ISBN-13: 9781584882558

Pub. Date: 09/12/2003

Publisher: Taylor & Francis

Offers the first treatment of automata aimed at undergraduates Provides a clear, classroom-tested presentation with an abundance of exercises Emphasizes motivation, both in developing the mathematics and in relation to applications Connects the material to areas such as combinatorial group theory and symbolic dynamics Interest in semigroup theory and automata is

Overview

Offers the first treatment of automata aimed at undergraduates Provides a clear, classroom-tested presentation with an abundance of exercises Emphasizes motivation, both in developing the mathematics and in relation to applications Connects the material to areas such as combinatorial group theory and symbolic dynamics Interest in semigroup theory and automata is currently on the rise, and the ideas of finite automata are becoming more accepted by the mathematical community. The time is now right to begin introducing those ideas to upper-level students in both mathematics and theoretical computer science. This book—the first of its kind—presents a well-motivated introduction to finite automata and semigroup theory and makes clear connections to other areas, including combinatorial group theory and symbolic dynamics as well as formal language theory and aspects of theoretical computer science. The author develops the underlying algebra gently but rigorously and includes more than 200 exercises with hints and solutions.

Product Details

ISBN-13:
9781584882558
Publisher:
Taylor & Francis
Publication date:
09/12/2003
Pages:
320
Product dimensions:
6.40(w) x 9.30(h) x 0.90(d)

Table of Contents

INTRODUCTION TO FINITE AUTOMATA
Alphabets and Strings
Languages
Language Operations
Finite Automata: Motivation
Finite Automata and their Languages
Summary of Chapter 1
Remarks on Chapter 1
RECOGNISABLE LANGUAGES
Designing Automata
Incomplete Automata
Automata which Count
Automate which Locate Patterns
Boolean Operations
The Pumping Lemma
Summary of Chapter 2
Remarks on Chapter 2
NON-DETERMINISTIC AUTOMATA
Accessible Automata
Non-Deterministic Automata
Applications
Trim Automata
Grammars
Summary of Chapter 3
Remarks on Chapter 3
e-AUTOMATA
Automata withe-Transitions
Applications of e-Automata
Summary of Chapter 4
Remarks on Chapter 4
KLEENE'S THEOREM
Regular Languages
Kleene's Theorem: Proof
Kleene's Theorem: algorithms
Language Equations
Summary of Chapter 5
Remarks on Chapter 5
LOCAL LANGUAGES
Myhill Graphs
Linearisation
Summary of Chapter 6
Remarks on Chapter 6
MINIMAL AUTOMATA
Partitions and Equivalence Relations
The Indistinguishability Relation
Isomorphisms of Automata
The Minimal Auomaton
The Method of Quotients
Summary of Chapter 7
Remarks on Chapter 7
THE TRANSITION MONOID
Functions on States
The Extended Transition Table
The Cayley Table of an Automaton
Semigroups and Monoids
Summary of Chapter 8
Remarks on Chapter 8
THE SYNTACTIC MONOID
Introduction to Semigroups
Congruences
The Transition Monoid of an Automaton
The Syntactic Monoid of a Language
Summary of Chapter 9
Remarks on Chapter 9
ALGEBRAIC LANGUAGE THEORY
Finite Semigroups
Recognisability by a Monoid
Two Counterexamples
Summary of Chapter 10
Remarks on Chapter 10
STAR-FREE LANGUAGES
Introduction
Groups
Aperiodic Semigroups
Schutzenberger's Theorem
An Example
Summary of Chapter 11
Remarks on Chapter 11
VARIETIES OF LANGUAGES
Pseudovarieties and Varieties
Summary of Chapter 12
Remarks on Chapter 12
APPENDIX: DISCRETE MATHEMATICS
Logic and Proofs
Set Theory
Numbers and Matrices
Graphs
Functions
Relations
BIBLIOGRAPHY
INDEX

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >