Finite Automata: 1st Edition (Hardback) book cover

Finite Automata

1st Edition

By Mark V. Lawson

Chapman and Hall/CRC

320 pages | 176 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781584882558
pub: 2003-09-17
SAVE ~$16.50
$110.00
$93.50
x
eBook (VitalSource) : 9780429175749
pub: 2003-09-17
from $28.98


FREE Standard Shipping!

Description

Interest in finite automata theory continues to grow, not only because of its applications in computer science, but also because of more recent applications in mathematics, particularly group theory and symbolic dynamics. The subject itself lies on the boundaries of mathematics and computer science, and with a balanced approach that does justice to both aspects, this book provides a well-motivated introduction to the mathematical theory of finite automata.

The first half of Finite Automata focuses on the computer science side of the theory and culminates in Kleene's Theorem, which the author proves in a variety of ways to suit both computer scientists and mathematicians. In the second half, the focus shifts to the mathematical side of the theory and constructing an algebraic approach to languages. Here the author proves two main results: Schützenberger's Theorem on star-free languages and the variety theorem of Eilenberg and Schützenberger.

Accessible even to students with only a basic knowledge of discrete mathematics, this treatment develops the underlying algebra gently but rigorously, and nearly 200 exercises reinforce the concepts. Whether your students' interests lie in computer science or mathematics, the well organized and flexible presentation of Finite Automata provides a route to understanding that you can tailor to their particular tastes and abilities.

Reviews

“… this book provides a well-motivated introduction to the mathematical theory of finite automata. … Accessible even to students with only a basic knowledge of discrete mathematics, this treatment develops the underlying algebra gently but rigorously, and nearly 200 exercises reinforce the concepts. Whether your students’ interests lie in computer science or mathematics, the well organized and flexible presentation of the book provides a route to understanding that you can tailor to their particular tastes and abilities. ”

— In Zentralblatt MATH, Vol. 1086, 2006/12

“Lawson’s book … is well written, self-contained, and quite extensive. The material is fully explained, with many examples fully discussed, and with many and varied exercises. … Students using this book will get a broad education in finite-automata theory.”

SIAM Review

“[This book] is a nice textbook intended for an undergraduate lecture. … All presented results are illustrated by many simple examples. … The book is self-contained and easy to read. It can be recommended as a textbook for undergraduate lectures about finite automata.”

EMS Newsletter

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

Subject Categories

BISAC Subject Codes/Headings:
COM046000
COMPUTERS / Operating Systems / General
MAT002000
MATHEMATICS / Algebra / General
MAT036000
MATHEMATICS / Combinatorics