文档介绍：Universitext
For other titles published in this series, go to
ies/223
Ian Chiswell
A Course in Formal
Languages, Automata
and Groups
ABC
Ian Chiswell
Department of Pure Mathematics
School of Mathematical Sciences
Queen Mary, University of London
London E1 4NS, UK
.******@
Editorial board:
Sheldon Axler, San Francisco State University
Vincenzo Capasso, Universit`a degli Studi di Milano
Carles Casacuberta, Universitat de Barcelona
Angus MacIntyre, Queen Mary, University of London
h Ribet, University of California, Berkeley
Claude Sabbah, CNRS, Ecole´ Polytechnique
Endre S¨uli, University of Oxford
Wojbor Woyczynski, ´ Case Western Reserve University
ISBN 978-1-84800-939-4 e-ISBN 978-1-84800-940-0
DOI -1-84800-940-0
British Library Cataloguing in Publication Data
A catalogue record for this book is available from the British Library
Library of Congress Control Number: 2008939035
Mathematics Subject Classification (2000): 03D10, 03D20, 20F10, 20F65, 68Q05, 68Q42, 68Q45
Hopcroft/Ullman, Formal Languages and Their Relation to Automata (adapted material from Chapter 5
(Section , Section , Theorem , Theorem , and Theorem ) and Chapter 12 (Theorem
and Theorem )), c 1969. Reproduced by permission of Pearson Education, Inc.
c Springer-Verlag London Limited 2009
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as
permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced,
stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers,
or in the case of reprographic reproduction in accordance with the terms of licenses issued by the
Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to
the publishers.
The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a
spe