Introduction to the Theory of
Computation, Third Edition
Michael Sipser
Editor-in-Chief: Marie Lee
Senior Product Manager:
Alyssa Pratt
Associate Product Manager:
Stephanie Lorenz
Content Project Manager:
Jennifer Feltri-George
Art Director: GEX Publishing Services
Associate Marketing Manager:
Shanna Shelton
Cover Designer: Wing-ip Ngan,
Ink design, inc
Cover Image Credit: @Superstock
© 2013 Cengage Learning
ALL RIGHTS RESERVED. No part of this work covered by the copy-
right herein may be reproduced, transmitted, stored or used in any
form or by any means graphic, electronic, or mechanical, including
but not limited to photocopying, recording, scanning, digitizing, tap-
ing, Web distribution, information networks, or information storage
and retrieval systems, except as permitted under Section 107 or 108
of the 1976 United States Copyright Act, without the prior written
permission of the publisher.States Copyright Act, without the prior
written permission of the publisher.
Library of Congress Control Number: 2012938665
ISBN-13: 978-1-133-18779-0
ISBN-10: 1-133-18779-X
Cengage Learning
20 Channel Center Street
Boston, MA 02210
USA
Cengage Learning is a leading provider of customized learning solu-
tions with office locations around the globe, including Singapore, the
United Kingdom, Australia, Mexico, Brazil, and Japan. Locate your
local office at: international.cengage.com/region
Cengage Learning products are represented in Canada by Nelson
Education, Ltd.
For your lifelong learning solutions, visit www.cengage.com
Cengage Learning reserves the right to revise this publication and
make changes from time to time in its content without notice.
The programs in this book are for instructional purposes only.
They have been tested with care, but are not guaranteed for any
particular intent beyond educational purposes. The author and
the publisher do not offer any warranties or representations,
nor do they accept any liabilities with respect to the programs.
Printed in the United States of America
1 2 3 4 5 6 7 8 16 15 14 13 12
For product information and technology assistance, contact us at
Cengage Learning Customer & Sales Support,
1-800-354-9706
For permission to use material from this text or product,
submit all requests online at cengage.com/permissions
Further permissions questions can be emailed to
permissionrequest@cengage.com
Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the
eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional
content at any time if subsequent rights restrictions require it.
