资源描述：
《6 structure of CFLs.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、6StructureofCFLs6.1IntroductionWhatcanbetheadditionstoafiniteautomatonsothatitmayacceptanycontext-freelanguage?Clearly,someadditionisrequiredaseachregularlanguageiscontext-freeandtherearecontext-freelanguagesthatarenotregular.Forexample,thelan-guageL={anbn:
2、n∈N}iscontext-freebutitisnotregular.Hereyoucanseethatsomehowtheautomatonmustrememberhowmanya’sithasread,andthenithastoconsumeb’soneafteranothermatchingtothatnumber.Afiniteautomatondoesnotrememberanything.So,wedonotseehowanautomatoncanacceptthelanguage{ww:w∈
3、{a,b}∗},wherewisthestringobtainedfromwbyinterchanginga’swithb’s.Weaddsomesortofmemorytoafiniteautomatonsothatitremembersthefirsthalfandthenmatchthatwiththesecondhalf,symbolbysymbol.Moreover,howwoulditknowthatithascomeacrossthefirsthalfoftheinputstring?Well,we
4、willkeepthatundeterminedsothattheautomatonwouldguessandthenwilldotherightthingwhenithastherightguess.Ifitisnottherightguess,thenthemachinewillnotbepenalizedforit.Anondeterministicmachinewithsomekindofmemorymightdothejob.6.2PushdownAutomataWestartwithsuchan
5、ondeterministicmachinewithaveryprimitivetypeofmemory,calledastackorapushdownstorage.Astackresembleskeepingbooksonyourtable,whereyoucanaddonemoreonthetoportakeoutonefromthetop.Weplantoaddsuchastacktoafiniteautomaton.Thesetwooperationsofaddingonemoreonthetop,
6、calledpushingtothestack,anddeletingonefromthetop,calledpoppingofffromthestack,areinbuilttoanystack.Toseehowthelanguage{anbn:n∈N}canbeacceptedbyanautomatonwithastack,thinkofanautomatonthataccepts{ambn:m,n∈N}andthengiveitthecapabilityofputtingonepebbleonthes
7、tackwhenanaisreadandthrowingonepebbleoutwhenabisread.So,thestackmustbeemptybeforetheautomatonstartsA.Singh,ElementsofComputationTheory,TextsinComputerScience,159cSpringer-VerlagLondonLimited20091606StructureofCFLsanditmustalsobeemptyattheendofitsworkforac
8、ceptingthestring.Thisstackalongwithafiniteautomatonfora∗b∗willaccept{ambm:m∈N}.Suchamachinehasafiniteinputtapecontainingitsinput.Thereadingheadreadsfromlefttorightonesymbolatatime,orevenitreadsnothingsometimes.
