A Course in Formal Languages, Automata and Groups
Based on the author’s lecture notes for an MSc course, this text combines formal language and automata theory and group theory, a thriving research area that has developed extensively over the last twenty-five years. The aim of the first three chapters is
- PDF / 1,831,122 Bytes
- 162 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 188 Views
For other titles published in this series, go to www.springer.com/series/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 [email protected] 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 Kenneth Ribet, University of California, Berkeley ´ Claude Sabbah, CNRS, Ecole Polytechnique Endre S¨uli, University of Oxford Wojbor Woyczy´nski, Case Western Reserve University
ISBN 978-1-84800-939-4 DOI 10.1007/978-1-84800-940-0
e-ISBN 978-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 4.2, Section 4.3, Theorem 5.1, Theorem 5.2, and Theorem 5.3) and Chapter 12 (Theorem 12.4 c 1969. Reproduced by permission of Pearson Education, Inc. and Theorem 12.9)), 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 specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Printed on acid-free paper Springer Science+Business Media springer.com
Preface
This book is based on notes for a master’s course given at Queen Mary, University of London, in the 1998/9 session. Such courses in London are quite short, and the course consisted essentially of the material in the first three chapters, together with a two-hour lecture on connections with group theory. Chapter 5 is a considerably expanded version of this. For the course, the main sources were the books by Hopcroft and Ullman ([20]), by Cohen ([4]), and by Epstein et al. ([7]). Some use was also made of a later book by Hopcroft and Ullman ([21]). The ulterior motive in the first three chapters is to give a rigorous proof that various notions of
Data Loading...
