Collapsing Nondeterministic Automata
With respect to minimization, the situation for nondeterministic automata is not as satisfactory as that for deterministic automata. For example, minimal NFAs are not necessarily unique up to isomorphism (Miscellaneous Exercise 60). However, part of the M
- PDF / 24,708,371 Bytes
- 407 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 200 Views
David Gries Fred B. Schneider
UNDERGRADUATE TEXTS IN COMPUTER SCIENCE Beidler, Data Structures and Algorithms Bergin, Data Structure Programming Brooks, C Programming: The Essentials for Engineers and Scientists Brooks, Problem Solving with Fortran 90 Dandamudi, Introduction to Assembly Language Programming Gril/meyer, Exploring Computer Science with Scheme Jalote, An Integrated Approach to Software Engineering, Second Edition Kizza, Ethical and Social Issues in the Information Age Kozen, Automata and Computability Merritt and Stix, Migrating from Pascal to C++ Pearce, Programming and Meta-Programming in Scheme Zeigler, Objects and Systems
Dexter C. Kozen
Automata and Computability
~ Springer
Dexter C. Kozen Department of Computer Science Cornell Uni versity Ithaca, NY 14853-7501 USA
Series Edirors DavidGries Department of Computer Science 415 Boyd Studies Research Center The University of Georgia Athens, Georgia 30602 USA
Fred B. Schneider Department of Computer Science Cornell University 4115C Upson Hall Ithaca, NY 14853-7501 USA
On rIUl cover: Cover photo taken by John Still/Photonica. With 1 figure. Library of Congress Cataloging-in-Publication Data Kozen, Dexter, 1951Automata IOd computability/Dexter C. Kozen. p. cm. - (Undergraduate texts in computer science) Includes bibliographical references IOd index. ISBN 978-1-4612-7309-7 ISBN 978-1-4612-1844-9 (eBook) DOI 10.1007/978-1-4612-1844-9 1. Machine theory. 2. Computable functions. I. Title. II. Series. QA267.K69 1997 511.3 - dc21 96-37409 Printed on acid-frec paper. © 1997 Springer Science+Business Media New York
Originally published by Springer-Verlag New York,lnc. in 1997 Softcover reprint ofthe hardcover lst edition 1997 AII rights reserved. This work may not be translated or copied in whole or in part withoot the written pennission of the publisher (Springer ScieDce+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for briefexcerpts in connection with reviews or scholarly analysis. Use in connection with any fOnD of information storage and retrieval, electronic adaptation, computer software, ar by similar ar dissimilar methodology now know ar hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is notto be taken as an expression of opinion as ta whether ar not they are subject ta proprietary rights.
987 ISBN 978-1-4612-7309-7 springeronline.com
To Juris
Preface
These are my lecture notes from C8381/481: Automata and Computability Theory, a one-semester senior-level course I have taught at Cornell University for many years. I took this course myself in the fall of 1974 as a first-year Ph.D. student at Cornell from Juris Hartmanis and have been in love with the subject ever since. The course is required for computer science majors at Cornell. It exists in two forms: C8481, an honors version; and C8381, a somewhat gentlerpaced version. The syllabus is roughly the same, but C8481 goes deeper into the subject, c
