资源描述：
《algebraic theory of automata and languages.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、AAlgebraicTh"'AutomataandThispageintentionallyleftblankAlgebraicThOfAutomataandLanguagesMasamiItovWorldScientificNEWJERSEYLONDONSINGAPORE.BElJlNG*SHANGHAIHONGKONG*TAIPEICHENNAIPublishedbyWorldScientificPublishingCo.Re.Ltd.5TohTuckLink,Singapore596224USAofice:S
2、uite202,1060MainStreet,RiverEdge,NJ07661UKofice:57SheltonStreet,CoventGarden,LondonWC2H9HEBritishLibraryCataloguing-in-PublicationDataAcataloguerecordforthisbookisavailablefromtheBritishLibrary.ALGEBRAICTHEORYOFAUTOMATAANDLANGUAGESCopyright02004byWorldScientifi
3、cPublishingCo.Re.Ltd.Allrightsreserved.Thisbookorpartsthereojmaynotbereproducedinanyformorbyanymeans,electronicormechanical,includingphotocopying,recordingoranyinformationstorageandretrievalsystemnowknownortobeinvented,withoutwrittenpermissionfromthePublisher.F
4、orphotocopyingofmaterialinthisvolume,pleasepayacopyingfeethroughtheCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers,MA01923,USA.Inthiscasepermissiontophotocopyisnotrequiredfromthepublisher.ISBN981-02-4727-3PrintedinSingaporebyWorldScientificPrinters(S)Pte
5、LtdInMemoryofProfessorJurgenDuskeThispageintentionallyleftblankPrefaceThetheoryofformallanguagesbeganwiththeclassificationoflan-guagesbyN.ChomskyinSyntacticStructuresin1957.Now,thisclassificationiscalledtheChomskyhierarchyoflanguages.Ontheotherhand,thetheoryofa
6、utomatawasinitiatedbyM.O.RabinandD.Scottin1959.Theirworkcanberegardedasthemostimportantfirststepinthetheoryofautomatainspiteofitssimplicity.Sincethen,thesetwofieldshavebeendevelopedbymanyre-searchersastwoimportanttheoreticalfoundationsofcomputersci-ence.Inthisb
7、ook,wewillmainlyhandleformallanguagesandau-tomatafromthealgebraicpointofview.Inthefirsttwochapters,wewillinvestigatethealgebraicstructureofautomataandthenwewilldealwithakindofglobaltheory,i.e.partiallyorderedsetsofautomata.Inthefollowingfourchapters,wewillstudy
8、grammars,languagesandoperationsonlanguages.Inthelastsection,wewillintroducespecialkindsofautomata,i.e.directableautomata.Thesubjectsinthebookseemtobeuniquecomparedtootherboo
