资源描述：
《regulated grammars with leftmost derivation》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、RegulatedGrammarswithLeftmostDerivation?HenningFernauWilhelm-Schickard-InstitutfurInformatik,UniversitatTubingenSand13,D-72076Tubingen,Germanyemail:fernau@informatik.uni-tuebingen.deAbstract.Inthispaper,weinvestigatevariousconceptsofleftmostderivationingrammarscontrolle
2、dbybicoloureddigraphs,especiallyre-gardingtheirdescriptivecapacity.Thisapproachallowsustounifythepresentationofknownresultsregardingespeciallyprogrammedgram-marsandmatrixgrammars,andtoobtainnewresultsconcerninggram-marswithregularcontrol,andperiodicallytime-variantgramm
3、ars.More-over,wegetnewresultsonleftmostderivationsinconditionalgrammars.1IntroductionAlthoughleftmostderivations(mostlyleftmostderivationsoftype3explainedbelow)playedavitalr^olewhenseveralrewritingmechanismshavebeende- nedataround1970,therehasbeennosystematicresearchint
4、hatdirection.Thisissurprising:aleftmostrestrictionmaybeameanstogetridoftheseem-inglyinherentnondeterminismfeatureingrammars,see[2],whichrendersthesemechanismshardtoapply.Westudyleftmostderivationsinregulatedrewritingsystematicallybyusingtheframeworkofgraph-controlledgra
5、mmars,whichareanintuitivelyappealingunifyingframeworkformanyseeminglydi erentwaysofregulation(see[7,9,10]).Hence,weobtainsimpli edversionsofknownandmanynewresultsonleftmostderivationinregulatedrewriting(comparetheSec-tion1.4in[5]).Moreover,suchsystematicstudyisusefultod
6、etectunexploredsub-areas,forexampleconcerningleftmostderivationintime-variantgrammars.Thispapercontinuesourpreviousworksonleftmostderivation,see[4,11].Theneedforsuchasystematicexpositionisunderlinedby[17]and[6],whereideasfromregulatedrewritingareappliedtoparsingtheoryan
7、ddatabasetheory,respectively,althoughthepapersindicatethattheknowledgeofbasicfactsinregulatedrewritingisnottoowidespread.Notethatin[17]programmedgrammarswithleft-1derivationsareusedwithoutnamingthemsuch.Conventions:denotesinclusion,denotesstrictinclusion.;denotestheem
8、ptyset.Theemptywordisdenotedby.Thelengthofawordxisdenotedbyjxj.WeconsidertwolanguagesL;Ltobeequali Lnfg=Lnf
