Introduction to Languages
and The Theory of
John C. Martin
North Dakota State University
mar91469 FM i-xii.tex i December 30, 2009 10:29am
INTRODUCTION TO LANGUAGES AND THE THEORY OF COMPUTATION, FOURTH EDITION
Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the
Americas, New York, NY 10020. Copyright c
2011 by The McGraw-Hill Companies, Inc. All rights reserved.
Previous editions c
2003, 1997, and 1991. No part of this publication may be reproduced or distributed in any
form or by any means, or stored in a database or retrieval system, without the prior written consent of The
McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic s torage or
transmission, or broadcast for dist ance learning.
Some ancillaries, including electronic and print components, may not be available to customers outside the
This book is printed on acid-free paper.
Vice President & Editor-in-Chief: Marty Lange
Vice President, EDP: Kimberly Meriwether David
Global Publisher: Raghothaman Srinivasan
Director of Development: Kristine Tibbetts
Senior Marketing Manager: Curt Reynolds
Senior Project Manager: Joyce Watters
Senior Production Supervisor: Laur a Fuller
Senior Media Project Manager: Tammy Juran
Design Coordinator: Brenda A. Rolwes
Cover Designer: Studio Montage, St. Louis, M issouri
(USE) Cover Image: c
Compositor: Laserwords Private Limited
Typeface: 10/12 Ti mes Roman
Printer: R. R. Donnelley
All credits appearing on page or at the end of the book are considered to be an extension of the copyright page.
Library of Congress Cataloging-in-Publication Data
Martin, John C.
Introduction to languages and the t heory of computation / John C. Martin.—4th ed.
Includes bibliographical references and index.
ISBN 978-0-07-319146-1 (alk. paper)
1. Sequential machine theory. 2. Computable functions. I. Title.
mar91469 FM i-xii.tex ii December 30, 2009 10:29am