## Automata TheoryThis 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 ? Sch tzenberger 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), Sch tzenberger'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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Mathematical Preliminaries | 1 |

Finite State Automata | 99 |

McNaughtonYamada Theorem | 121 |

Chomsky Grammars | 147 |

Formal Power Series | 215 |

Turing Machines | 249 |

Pushdown Automata | 299 |

ContextSensitive Type1 Languages | 329 |

Lindenmeyer Developmental A Systems Syntactic | 369 |

Appendices | 387 |

Turing Machine and Complexity | 400 |

References | 419 |

### Other editions - View all

### Common terms and phrases

0Va 0Vz 0Va a a b aaabbbccc ABCDE ABCDEF accept algebraic Automata Theory Chapter Chomsky Normal Form compute construct contains an idempotent context-free grammar context-free languages context-sensitive context-sensitive languages corresponds Definition deterministic DFSA equivalent Example Figure finite set fN fN formal power series given the following grammar G halt hand side homomorphism idempotent input string inverse Kuroda Normal Form linear Linear-Bounded automaton LR(k matrix Maximal Subgroup Modal Logics NDFSA Negro non-terminal Normal Form Note parse parser polynomial production rules Pushdown Automata recursive regular expressions replace Schutzenberger Maximal Subgroup semigroup Sequential Machines Step sub-Turing machines symbols tape transition table Turing machine Д 1 Д Д Д Д ДД ху

### References to this book

Algebraic Theory of Automata Networks: A Introduction Pál Dömösi,Chrystopher L. Nehaniv No preview available - 2005 |