Solve the problems in hw2.pdfTextbook provided below
Introduction to the Theory of Computation This is an electronic version of the print textbook. Due to electronic rights restrictions, some third party content may be suppressed. Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.cengage.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest. 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. http://www.cengage.com/highered I n t ro duc t ion to the Theory o f ompu tatioC N t h i r d E d i t i o N m i C h a E l s i p s E r Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States 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. 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. http://www.cengage.com mailto:permissionrequest@cengage.com To Ina, Rachel, and Aaron 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. 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. C O N T E N T S Preface to the First Edition xi To the student . . . . . . . . . . . . . . . . . . . . . . . . . . . xi To the educator . . . . . . . . . . . . . . . . . . . . . . . . . . xii The first edition . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Feedback to the author . . . . . . . . . . . . . . . . . . . . . . xiii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . xiv Preface to the Second Edition xvii Preface to the Third Edition xxi 0 Introduction 1 0.1 Automata, Computability, and Complexity . . . . . . . . . . . . . 1 Complexity theory . . . . . . . . . . . . . . . . . . . . . . . . . 2 Computability theory . . . . . . . . . . . . . . . . . . . . . . . 3 Automata theory . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0.2 Mathematical Notions and Terminology . . . . . . . . . . . . . . 3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Sequences and tuples . . . . . . . . . . . . . . . . . . . . . . . 6 Functions and relations . . . . . . . . . . . . . . . . . . . . . . 7 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Strings and languages . . . . . . . . . . . . . . . . . . . . . . . 13 Boolean logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Summary of mathematical terms . . . . . . . . . . . . . . . . . 16 0.3 Definitions, Theorems, and Proofs . . . . . . . . . . . . . . . . . 17 Finding proofs . . . . . . . . . . . . . . . .