[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
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,1
Directedgraphs Adirectedgraph(ordigraph),alsodenotedG=(V,E),consistsofafinitesetof verticesVandasetoforderedpairsofverticesEcalledarcs.Wedenoteanarc fromvtowbyv->w.AnexampleofadigraphappearsinFig.1.2.quotesdbs_dbs10.pdfusesText_16
[PDF] Introduction to automata theory, languages, and computation - Sharif