Automatas

This page intentionally left blank

Automata Theory with Modern Applications
Recent applications to biomolecular science and DNA computing have created a new audience for automata theory and formal languages. This is the only introductory book to cover such applications. It begins with a clear and readily understood exposition of the basic principles, that assumes only a background in discretemathematics. The first five chapters give a gentle but rigorous coverage of regular languages and Kleene’s Theorem, minimal automata and syntactic monoids, Turing machines and decidability, and explain the relationship between context-free languages and pushdown automata. They include topics not found in other texts at this level, including codes, retracts, and semiretracts. The many examples andexercises help to develop the reader’s insight. Chapter 6 introduces combinatorics on words and then uses it to describe a visually inspired approach to languages that is a fresh but accessible area of current research. The final chapter explains recently-developed language theory coming from developments in bioscience and DNA computing. With over 350 exercises (for which solutions are available),plenty of examples and illustrations, this text will be welcomed by students as a contemporary introduction to this core subject; others, new to the field, will appreciate this account for self-learning.

Automata Theory with Modern Applications
With contributions by Tom Head

JAMES A. ANDERSON University of South Carolina Upstate

   Cambridge, New York, Melbourne, Madrid,Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge  , UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521848879 © Cambridge University Press 2006 This publication is in copyright. Subject to statutory exception and to the provision of relevantcollective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2006 - - - - - - ---- eBook (EBL) --- eBook (EBL) ---- hardback --- hardback ---- paperback --- paperback

Cambridge UniversityPress has no responsibility for the persistence or accuracy of s for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Contents

Preface 1 1.1 1.2 1.3 1.4 2 2.1 2.2 2.3 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 4 4.1 4.2 4.3 4.4 5 5.1 Introduction Sets Relations FunctionsSemigroups Languages and codes Regular languages Retracts (Optional) Semiretracts and lattices (Optional) Automata Deterministic and nondeterministic automata Kleene’s Theorem Minimal deterministic automata and syntactic monoids Pumping Lemma for regular languages Decidability Pushdown automata Mealy and Moore machines Grammars Formal grammars Chomsky normal form and Greibach normal form Pushdownautomata and context-free languages The Pumping Lemma and decidability Turing machines Deterministic Turing machines v

page vii 1 1 6 12 16 23 23 29 34 37 37 52 72 84 86 89 99 114 114 138 149 162 169 169

vi

Contents

5.2 5.3 5.4 6 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 7 7.1 7.2 7.3 7.4 7.5 7.6

Nondeterministic Turing machines and acceptance of context-free languages The halting problem for Turingmachines Undecidability problems for context-free languages A visual approach to formal languages Introduction A minimal taste of word combinatorics The spectrum of a word with respect to a language The spectral partition of + and the support of L Visualizing languages The sketch parameters of a language Flag languages Additional tools from word combinatorics Counting primitive words in a...