Automata Theory [Hardcover]

Matthew Simon (Author)

Book Description

ISBN-10: 9810237537 | ISBN-13: 978-9810237530 | Publication Date: July 15, 1999 | Edition: 1st

This volume covers substantially the central areas of a one-semester course in automata theory. It is oriented towards a mathematical perspective that is understandable to non-mathematicians. Comprehension is greatly aided by examples. Special attention is given to semi-automata theory - the relationship between semigroups and sequential machines (including Green's relations), Schutzenberger's maximal subgroup, von Neumann inverses, wreath products, transducers using matrix notation, shuffle and Kronecker shuffle products. Methods of formal power series, the ambiguity index and linear languages are discussed. Core material includes finite state automata, regular expressions, Kleene's theorem, Chomsky's hierarchy and transformations of grammars. Ambiguous grammars (not linited to context-free grammars) and modal logics are briefly discussed. Turing machine variants with many examples, pushdown automata and their state transition diagrams and parsers, linear bounded automata/2-PDA and Kuroda normal form are also discussed. A brief study of Lindenmeyer systems is offered as a comparison to the theory of Chomsky.

Product Details

• Hardcover: 428 pages
• Publisher: World Scientific Pub Co Inc; 1st edition (July 15, 1999)
• Language: English
• ISBN-10: 9810237537
• ISBN-13: 978-9810237530
• Product Dimensions: 9.9 x 6.8 x 0.9 inches
• Shipping Weight: 2 pounds (View shipping rates and policies)
• Average Customer Review: 2.7 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #2,305,787 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

6 of 7 people found the following review helpful:

1.0 out of 5 stars Not to be used as an introductiory text, May 15, 2001

By A Customer

This review is from: Automata Theory (Hardcover)

Based on this book I tried to get introduced into the field of automata theory. But, alas, this was a complete failure: This book comes with nearly no text between the formulae (and I'm not afraid of formulae!) so there's NO way to understand the stuff introduced in this book. An example: In the first chapter semigroups were introduced and it wasn't clear at all what the relationship to sequential automata is. To summarize: If you need an introductiory text: Don't use this, this is more a collection of formulae probably helpful for the expert but not for starters.

6 of 9 people found the following review helpful:

2.0 out of 5 stars Too concise and lacking in examples., June 30, 1999

By A Customer

This review is from: Automata Theory (Hardcover)

The book uses not-so-common mathematical conventions which makes the reading hard. A more comprehensive book would show students how to work out the kinds of problems that are given at the end of each chapter. Most theorems are stated but are not proven (or the proof is described scantily) and by and large the book is a collection of statements about grammars, FSAs, Turing machines etc. It lacks an educational flow. The excerpts in the beginning of each chapter from the lives of Central-American slave owners are completely uncalled for.

3 of 8 people found the following review helpful:

5.0 out of 5 stars A Welcome Change, August 15, 1999

By A Customer

This review is from: Automata Theory (Hardcover)

Automata Theory by Matthew Simon is an unusually welcome book. The many examples shown include subjects not often covered, such as: the Chomsky-Schutzenberger Theorem, Kuroda Normal Forms, Ginsberg-Griebach Theorem, Simple Pushdown Automata, Syntactic Pattern Recognition, and Shape Grammers. The use of a consistent and standard notation throughout the book is also welcome, as many different subjects are discussed. The focus of the first chapter is upon Semigroups and Automata Theory(including wreath products), from a more elementary, less abstract, less mathematical viewpoint than that found in the dozen or so books covering this subject. Thus examples from automata theory are emphasized. While departures from the notation of Clifford and Preston do take place, the notation is as close as one can come to being standard, as no standard notation currently exists. Each chapter starts with a commentary or quotes relating to subjects that arise in socially oriented linguistics and automata theory. Such commentary is often omitted in books covering automata theory but is of interest to people studying Anthropological Linguistics, General (historical)Linguistics, Philosophical Linguistics, and other academic areas dealing with linguistics, but often neglected by the engineering, Computer Science and Mathematics communities.