Theory of Computation
INTRODUCTION TO THE THEORY OF COMPUTATION, SECOND EDITION
MICHAEL SIPSER
MassachusettsInstitute of Technology
THOMSON
COURSE TECHNOLOGY
Australia * Canada * Mexico * Singapore * Spain * United Kingdom * United States
THOIVISON
COURSE TECHNOLOGY
Introduction to the Theory of Computation, Second Edition by Michael Sipser
Senior Product Manager: Alyssa Pratt Executive Editor: Mac Mendelsohn Associate Production Manager: Aimee Poirier Senior Marketing Manager: Karen Seitz COPYRIGHT © 2006 Thomson Course Technology, a division of Thomson Learning, Inc. Thomson LearningTM is a trademark used herein under license. Printed in the United States of America 1 2 3 45 67 89 QWT 0908070605 For more information, contact Thomson Course Technology 25 Thomson Place Boston, Massachusetts, 02210. Or find us on the World Wide Web at: www.course.com ALL RIGHTS RESERVED. No part of this work covered by the copyright hereon may be reproduced or used in any form or by any means graphic, electronic, or mechanical, including photocopying, recording, taping, Web distribution, or information storage and retrieval systems without the written permission of the publisher.
Associate Product Manager: Mirella Misiaszek Editorial Assistant: Jennifer Smith Senior Manufacturing Coordinator: Trevor Kallop Cover Designer: Steve Deschesne For permission to use material from this text or product, submit a request online at http://www.thomsonrights.com Any additional questions about permissions can be submitted by e-mail to thomsonrights~thomson.com Disclaimer Thomson Course Technology reserves the right to revise this publication and make changes from time to time in its content without notice. ISBN 0-534-95097-3
To Ina, Rachel, and Aaron
CONTENTS
Preface to the First Edition xi To the student .... ...................................... xi To the educator ..................................... xii The first edition ..... .................................... xiii Feedback
MICHAEL SIPSER
MassachusettsInstitute of Technology
THOMSON
COURSE TECHNOLOGY
Australia * Canada * Mexico * Singapore * Spain * United Kingdom * United States
THOIVISON
COURSE TECHNOLOGY
Introduction to the Theory of Computation, Second Edition by Michael Sipser
Senior Product Manager: Alyssa Pratt Executive Editor: Mac Mendelsohn Associate Production Manager: Aimee Poirier Senior Marketing Manager: Karen Seitz COPYRIGHT © 2006 Thomson Course Technology, a division of Thomson Learning, Inc. Thomson LearningTM is a trademark used herein under license. Printed in the United States of America 1 2 3 45 67 89 QWT 0908070605 For more information, contact Thomson Course Technology 25 Thomson Place Boston, Massachusetts, 02210. Or find us on the World Wide Web at: www.course.com ALL RIGHTS RESERVED. No part of this work covered by the copyright hereon may be reproduced or used in any form or by any means graphic, electronic, or mechanical, including photocopying, recording, taping, Web distribution, or information storage and retrieval systems without the written permission of the publisher.
Associate Product Manager: Mirella Misiaszek Editorial Assistant: Jennifer Smith Senior Manufacturing Coordinator: Trevor Kallop Cover Designer: Steve Deschesne For permission to use material from this text or product, submit a request online at http://www.thomsonrights.com Any additional questions about permissions can be submitted by e-mail to thomsonrights~thomson.com Disclaimer Thomson Course Technology reserves the right to revise this publication and make changes from time to time in its content without notice. ISBN 0-534-95097-3
To Ina, Rachel, and Aaron
CONTENTS
Preface to the First Edition xi To the student .... ...................................... xi To the educator ..................................... xii The first edition ..... .................................... xiii Feedback