[PDF] [PDF] Intro To Automata Theory Languages And Computation John E

View - Download [PDF] Intro To Automata Theory Languages And Computation John E

Previous PDF

Next PDF

INllHHXXTION

AL'lttMATATIH-'OKY,

KankImnncKKmnDblIviy

KTUNOTES.INDownloaded from Ktunotes.in

INTRODUCTION

TOAUTOMATATHEORY,LANGUAGES,

COMPUTATION

JOHNE.HOPCROFT

CornellUniversity

JEFFREYD.ULLMAN

PrincetonUniversity

ADDISON-WESLEYPUBLISHINGCOMPANY

Reading,MassachusettsMenloPark,California

London•Amsterdam•DonMills,Ontario•Sydney

KTUNOTES.INDownloaded from Ktunotes.in

Thisbookisinthe

ADDISON-WESLEYSERIESINCOMPUTERSCIENCE

MichaelA.Harrison,

ConsultingEditor

LibraryofCongressCataloginginPublicationData

Hopcroft,JohnE.,1939-

Introductiontoautomatatheory,languages,and

computation.

Bibliography:p.

Includesindex.

1.Machinetheory.2.Formallanguages.

3-Computationalcomplexity.I.Ullman,

JeffreyD.,19^2-jointauthor.II.Title.

QA267.H56629.8'31278-67950

ISBN0-201-02988-X

Copyright(O1979by

Addison-WesleyPublishingCompany,Inc.

Philippinescopyright1979by

Addison-WesleyPublishingCompany,Inc.

Allrightsreserved.Nopartofthispublicationmay

bereproduced,storedinaretrievalsystem,or transmitted,inanyformorbyanymeans, electronic,mechanical,photoc6pying,recording,or otherwise,withoutthepriorwrittenpermissionof thepublisher.PrintedintheUnitedStatesof

America.PublishedsimultaneouslyinCanada.

LibraryofCongressCatalogCardNo.78-67950.

ISBN:0-201-02988-X

LMNOPQ-DO-89876

KTUNOTES.IN

Downloaded from Ktunotes.in

PREFACE

Tenyearsagotheauthorsundertooktoproduceabookcoveringtheknownmaterialon formallanguages,automatatheory,andcomputationalcomplexity.Inretrospect,onlya fewsignificantresultswereoverlookedinthe237pages.Inwritinganewbookonthe subject,wefindthefieldhasexpandedinsomanynewdirectionsthatauniformcom- prehensivecoverageisimpossible.Ratherthanattempttobeencyclopedic,wehavebeen brutalinoureditingofthematerial,selectingonlytopicscentraltothetheoretical developmentofthefieldorwithimportancetoengineeringapplications. Overthepasttenyearstwodirectionsofresearchhavebeenofparamountim- portance.Firsthasbeentheuseoflanguage-theoryconcepts,suchasnondeterminismand thecomplexityhierarchies,toprovelowerboundsontheinherentcomplexityofcertain practicalproblems.Secondhasbeentheapplicationoflanguage-theoryideas,suchas regularexpressionsandcontext-freegrammars,inthedesignofsoftware,suchascompilers andtextprocessors.Bothofthesedevelopmentshavehelpedshapetheorganizationof thisbook.

USEOFTHEBOOK

BothauthorshaveusedChapters1through8forasenior-levelcourse,omittingonlythe materialoninherentambiguityinChapter4andportionsofChapter8.Chapters7,8,

12,and13formthenucleusofacourseoncomputationalcomplexity.Anadvanced

courseonlanguagetheorycouldbebuiltaroundChapters2through7,9through11, and14.

EXERCISES

Weusetheconventionthatthemostdifficultproblemsaredoublystarred,andproblems ofintermediatedifficultyareidentifiedbyasinglestar.ExercisesmarkedwithanShave v

KTUNOTES.IN

Downloaded from Ktunotes.in

VIPREFACE

solutionsattheendofthechapter.Wehavenotattemptedtoprovideasolutionmanual, buthaveselectedafewexerciseswhosesolutionsareparticularlyinstructive.

ACKNOWLEDGMENTS

Wewouldliketothankthefollowingpeoplefortheirperceptivecommentsandadvice: AlAho,NissimFrancez,JonGoldstine,JurisHartmanis,DaveMaier,FredSpringsteel, andJacoboValdes.ThemanuscriptwasexpertlytypedbyMarieOltonandAprilRoberts atCornellandGerreePechtatPrinceton.

Ithaca,NewYork

Princeton,NewJersey

March1979J.E.H.

J.D.U.

KTUNOTES.INDownloaded from Ktunotes.in

CONTENTS

Chapter1Preliminaries

1.1Strings,alphabets,andlanguages1

1.2Graphsandtrees2

1.3Inductiveproofs4

1.4Setnotation5

1.5Relations6

1.6Synopsisofthebook8

Chapter2FiniteAutomataandRegularExpressions

2.1Finitestatesystems13

2.2Basicdefinitions16

2.3Nondeterministicfiniteautomata19

2.4Finiteautomatawith(-moves24

2.5Regularexpressions28

2.6Two-wayfiniteautomata36

2.7Finiteautomatawithoutput42

2.8Applicationsoffiniteautomata45

Chapter3PropertiesofRegularSets

3.1Thepumpinglemmaforregularsets55

3.2Closurepropertiesofregularsets58

3.3Decisionalgorithmsforregularsets63

3.4TheMyhill-Nerodetheoremandminimizationoffiniteautomata..65

vii

KTUNOTES.IN

Downloaded from Ktunotes.in

VliiCONTENTS

Chapter4Context-FreeGrammars

4.1Motivationandintroduction77

4.2Context-freegrammars79

4.3Derivationtrees82

4.4Simplificationofcontext-freegrammars87

4.5Chomskynormalform92

4.6Greibachnormalform94

4.7Theexistenceofinherentlyambiguouscontext-freelanguages...99

Chapter5PushdownAutomata

5.1Informaldescription107

5.2Definitions108

5.3Pushdownautomataandcontext-freelanguages114

Chapter6PropertiesofContext-FreeLanguages

6.1ThepumpinglemmaforCFL's125

6.2ClosurepropertiesofCFL's130

6.3DecisionalgorithmsforCFL's137

Chapter7TuringMachines

7.1Introduction146

7.2TheTuringmachinemodel147

7.3Computablelanguagesandfunctions150

7.4TechniquesforTuringmachineconstruction153

7.5ModificationsofTuringmachines159

7.6Church'shypothesis166

7.7Turingmachinesasenumerators167

7.8RestrictedTuringmachinesequivalenttothebasicmodel170

Chapter8Undecidability

8.1Problems177

8.2Propertiesofrecursiveandrecursivelyenumerablelanguages...179

8.3UniversalTuringmachinesandanundecidableproblem181

8.4Rice'stheoremandsomemoreundecidableproblems185

8.5UndecidabilityofPost'scorrespondenceproblem193

8.6ValidandinvalidcomputationsofTM's:atoolforproving

CFLproblemsundecidable201

8.7Greibach'stheorem205

8.8Introductiontorecursivefunctiontheory207

8.9Oraclecomputations209

Chapter9TheChomskyHierarchy

9.1Regulargrammars217

9.2Unrestrictedgrammars220

KTUNOTES.INDownloaded from Ktunotes.in

CONTENTSIX

9.3Context-sensitivelanguages223

9.4Relationsbetweenclassesoflanguages227

Chapter10DeterministicContext-FreeLanguages

10.1NormalformsforDPDA's234

10.2ClosureofDCFL'sundercomplementation235

10.3Predictingmachines240

10.4AdditionalclosurepropertiesofDCFL's243

10.5DecisionpropertiesofDCFL's246

10.6LR(0)grammars248

10.7LR(0)grammarsandDPDA's252

10.8LR(k)grammars260

Chapter11ClosurePropertiesofFamiliesofLanguages

11.1Triosandfulltrios270

11.2Generalizedsequentialmachinemappings272

11.3Otherclosurepropertiesoftrios276

11.4Abstractfamiliesoflanguages277

11.5IndependenceoftheAFLoperations279

11.6Summary279

Chapter12ComputationalComplexityTheory

12.1Definitions285

12.2Linearspeed-up,tapecompression,andreductionsinthenumber

oftapes288

12.3Hierarchytheorems295

12.4Relationsamongcomplexitymeasures300

12.5Translationallemmasandnondeterministichierarchies302

12.6Propertiesofgeneralcomplexitymeasures:thegap,speedup,

anduniontheorems306

12.7Axiomaticcomplexitytheory312

Chapter13IntractableProblems

13.1Polynomialtimeandspace320

13.2SomeNP-completeproblems324

13.3Theclassco-./T^341

13.4PSPACE-completeproblems343

13.5Completeproblemsfor&andNSPACE(logn)347

13.6Someprovablyintractableproblems350

13.7The0> - jV'i?questionforTuringmachineswithoracles:

limitsonourabilitytotellwhether&=c\'d?362 Chapter14HighlightsofOtherImportantLanguageClasses

14.1Auxiliarypushdownautomata377

14.2Stackautomata381

KTUNOTES.INDownloaded from Ktunotes.in

XCONltNlb

14.3Indexedlanguages389

14.4Developmentalsystems390

Bibliography396

Index411

KTUNOTES.INDownloaded from Ktunotes.in

CHAPTER

1

PRELIMINARIES

Inthischapterwesurveytheprincipalmathematicalideasnecessaryforunder- standingthematerialinthisbook.Theseconceptsincludegraphs,trees,sets, relations,strings,abstractlanguages,andmathematicalinduction.Wealsopro- videabriefintroductionto,andmotivationfor,theentirework.Thereaderwitha backgroundinthemathematicalsubjectsmentionedcanskiptoSection1.6for motivationalremarks.

1.1STRINGS,ALPHABETS,ANDLANGUAGES

A"symbol"isanabstractentitythatweshallnotdefineformally,justas"point" and"line"arenotdefinedingeometry.Lettersanddigitsareexamplesof frequentlyusedsymbols.Astring(orword)isafinitesequenceofsymbolsjux- taposed.Forexample,a,b,andcaresymbolsandabcbisastring.Thelengthofa stringw,denoted|w |,isthenumberofsymbolscomposingthestring.Forexam- ple,abcbhaslength4.Theemptystring,denotedby£,isthestringconsistingof zerosymbols.Thus\e\=0. Aprefixofastringisanynumberofleadingsymbolsofthatstring,anda suffixisanynumberoftrailingsymbols.Forexample,stringabchasprefixes£,a,ab, andabc;itssuffixesare£,c,be,andabc.Aprefixorsuffixofastring,otherthanthe stringitself,iscalledaproperprefixorsuffix. Theconcatenationoftwostringsisthestringformedbywritingthefirst, followedbythesecond,withnointerveningspace.Forexample,theconcatena- tionofdogandhouseisdoghouse.Juxtapositionisusedastheconcatenation operator.Thatis,ifwandxarestrings,thenwxistheconcatenationofthesetwo 1

KTUNOTES.IN

Downloaded from Ktunotes.in

2PRELIMINARIES

strings.Theemptystringistheidentityfortheconcatenationoperator.Thatis,

£w=we - wforeachstringw.

Analphabetisafinitesetofsymbols.A(formal)languageisasetofstringsof symbolsfromsomeonealphabet.Theemptyset,0,andthesetconsistingofthe emptystring{e}arelanguages.Notethattheyaredistinct;thelatterhasamember whiletheformerdoesnot.Thesetofpalindromes(stringsthatreadthesame forwardandbackward)overthealphabet{0,1}isaninfinitelanguage.Some membersofthislanguagearee,0,1,00,11,010,and1101011.Notethatthesetof allpalindromesoveraninfinitecollectionofsymbolsistechnicallynotalanguage becauseitsstringsarenotcollectivelybuiltfromanalphabet. AnotherlanguageisthesetofallstringsoverafixedalphabetZ.Wedenote thislanguagebyZ*.Forexample,ifZ={a},thenZ*={e,a,aa,aaa,...}.If

Z={0,1},thenZ*={e,0,1,00,01,10,11,000,...}.

1.2GRAPHSANDTREES

Agraph,denotedG=(V,E),consistsofafinitesetofvertices(ornodes)Vanda setofpairsofverticesEcallededges.AnexamplegraphisshowninFig.1.1.Here

V={1,2,3,4,5}andE={(n,m)|n+m=4orn+m=7}.

Fig.1.1Exampleofagraph.

Apathinagraphisasequenceofverticesvl9v2,...,vk,k>1,suchthatthere isanedge(vhvi+1)foreachi,1Directedgraphs Adirectedgraph(ordigraph),alsodenotedG=(V,E),consistsofafinitesetof verticesVandasetoforderedpairsofverticesEcalledarcs.Wedenoteanarc fromvtowbyv->w.AnexampleofadigraphappearsinFig.1.2.quotesdbs_dbs10.pdfusesText_16

[PDF] introduction to baking pdf

[PDF] introduction to balance sheet pdf

[PDF] introduction to basic programming language pdf

[PDF] introduction to big data pdf

[PDF] introduction to blackboard collaborate

[PDF] introduction to blockly

[PDF] introduction to bluej

[PDF] introduction to braille

[PDF] introduction to business administration textbook pdf

[PDF] introduction to business finance

[PDF] introduction to business law multiple choice questions

[PDF] introduction to business law multiple choice questions pdf

[PDF] introduction to business management notes pdf

[PDF] introduction to business notes pdf

[PDF] introduction to business pdf 2018