Automata Theory

Automata Theory

By: Matthew Simon (author)Hardback

Up to 2 WeeksUsually despatched within 2 weeks

Description

This book covers substantially the central ideas 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 many examples, especially on the Chomsky - Schutzenberger theorem, which is not found in most books in this field. Special attention is given to semiautomata 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 limited 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.

Contents

Mathematical preliminaries; sequential machines; finite state automata; Chomsky grammars; formal power series; Turing machines; pushdown automata; context-sensitive (Type-1) languages; Lindenmeyer (developmental) L systems, syntactic pattern recognition and shape grammars.

Product Details

  • ISBN13: 9789810237530
  • Format: Hardback
  • Number Of Pages: 440
  • ID: 9789810237530
  • ISBN10: 9810237537

Delivery Information

  • Saver Delivery: Yes
  • 1st Class Delivery: Yes
  • Courier Delivery: Yes
  • Store Delivery: Yes

Prices are for internet purchases only. Prices and availability in WHSmith Stores may vary significantly

Close