一种新的接受类 IPV4地址的有限自动机设计方法(IJMSC-V5-N1-6)

I.J.MathematicalSciencesandComputing,2019,1,65-79PublishedOnlineJanuary2019inMECS()DOI:10.5815/ijmsc.2019.01.06Availableonlineat*,K.S.Sravan2,M.S.Chakravarthy31,2,3DepartmentofComputerScienceandEngineering,GodavariInstituteofEngineeringandTechnology(A),Rajahmundry,AndhraPradesh,India.Received:19April2018;Accepted:06August2018;Published:08January2019AbstractTheoryofcomputationischaracterizedascalculationthroughtheconceptualmachines.ThethreeessentialuniquemachinesutilizedareFiniteAutomata,PushdownAutomataandTuringMachine.InthispaperweproposeanoutlineofFiniteAutomatathatacceptstheclassofIPV4Addresses.IndexTerms:FiniteAutomata,IPAddress.©2019PublishedbyMECSPublisher.Selectionand/orpeerreviewunderresponsibilityoftheResearchAssociationofModernEducationandComputerScience1.IntroductionTheoryofcomputationisdefinedascomputationthroughtheabstractmachines.FiniteAutomataisoneamongtheprimaryabstractmachines.Itisrepresentedasafivetuplemachine‘M’.M=(Q,∑,δ,S,F)Q–FiniteSetofStates∑–FiniteSetofInputSymbols(alphabets)δ–TransitionFunction(Q×∑→Q)S–InitialState(S∈Q)F–FinalState(F⊆Q)*Correspondingauthor.E-mailaddress:[e-mail]66ANewApproachtotheDesignofaFiniteAutomatonthatacceptsClassofIPV4Addresses1.1.AlphabetsAnalphabetisafinite,nonemptysetofinputsusuallydenotedas∑.ExamplesofthealphabetsBinaryalphabet∑={0,1}Englishalphabet∑={a,b,…,z}StringsAstring(orword)isafinitesequenceofsymbolsfromanalphabet.Forexample---1011isastringfromthebinaryalphabet∑={0,1}.Emptystringastringwithzerooccurrencesofsymbols.Length‘|W|’ofstring‘W’isdefinedasthenumberofpositionsforsymbolsinW.Forexamplelengthofthestring‘0111’is|0111|=4,Lengthofthestring‘’is||=0.Setofallstringsover∑isusuallydenotedas∑*i.e.,∑*=∑0∪∑1∪*2∪…∑n∑+=thesetofnonemptystringsfrom∑=∑*{}.Therefore,wehave∑+=∑1∪∑2∪∑3∪…∑nand∑*=∑+∪{}LanguagesAlanguageisasetofstringsallchosenfromsome∑*.Inotherwords,if∑isanalphabet,andL∑*,thenLisalanguageover∑.Examples:ForthelanguageL:SetofalllegalEnglishwords,∑={thesetofallletters}ForthelanguageL:Programwrittenin‘C’Language,∑={asubsetoftheASCIIcharacters}Thesetofallstringsofn0’sfollowedbyn1’sforn0:{,01,0011,000111,…}∑*isaninfinitelanguageforanyalphabet∑.∅Denotestheemptylanguage(nottheemptystring)whichisalanguageoveranyalphabet.{}isalanguageoveranyalphabet(consistingofonlyonestring,theemptystring).DifferentwaysofdescribinglanguagesDescriptionbyexhaustivelistingL1={a,ab,abc}(finitelanguage;listedonebyone)L2={a,ab,abb,abbb,...}(infinitelanguage;listedpartially)L3=L(ab*)(infinitelanguage;expressedbyaregularexpression)DescriptionbygenericelementsL4={x|xisoverV={a,b},beginswitha,followedbyanynumberofb,possiblenone}Note:L4=L3=L2ANewApproachtotheDesignofaFiniteAutomatonthatacceptsClassofIPV4Addresses67DescriptionbyintegerparametersL5={abn|n0}Note:L5=L4=L3=L2ClosuresoflanguageL:PositiveclosureofalanguageLisusuallydenotedasL+=L1∪L2∪…LnStarClosureofalanguageLisusuallydenotedasL*=0iiL=L0∪L1∪L2∪…LnNote:L*L0=L*–{1.2.InternetProtocol(IP)AddressesandAutomataThekeycontributiontothisresearchpaperstartswiththebasicideaaboutIPV4addressesandidentifyingtherequiredrelationshipsbetweenIPV4addressandConstructingFiniteAutomata.Usuallythecommunicationbetweenthecomputerscanbedonethroughthenetwork.Foranylevelofcommunicationweneedaglobaladdressingschemei.e.,IPaddressingschemetomeanalogicaladdressinthenetworklayeroftheTCP/IPprotocolsuite.TheseaddressesarereferredtoasIPV4addresses.AnIPV4addressisa32bitaddressthatuniquelydefinestheconnectionofadevicethroughInternet.TheaddressspaceoftheIPV4addressis232addresses(4,294,967,296addressesareavailable).AnIPV4addresscanberepresentedasbinarynotationanddotted-decimalnotation.ThefollowingFig.1depictsthenotationsoftheIPV4address.Fig.1.BinaryandDotted-DecimalNotationsoftheIPV4address.1.3.ClassfulAddressingSinceitsinception,theIPV4addressingusedtheconceptofclasses.Inclassfuladdressing,theaddressspaceisdividedintofiveclassesnamelyA,B,C,DandE.Eachclassoccupiessomepartoftheaddressspace.Wecanfindtheclassofanaddresswhenitisrepresentedinbinaryordotted-decimalnotations.ThefirstfewbitsinbinarynotationofIPaddresswilltellustheclassname.Thefirstbyteindotted-decimalnotationofIPaddressalsotellsustheclass.ThefollowingFig.2depictsboththemethods.AsfarasthefiniteautomatonisconcernedweuseonlybinarynotationofIPaddresstodetectitsclass.68ANewApproachtotheDesignofaFiniteAutomatonthatacceptsClassofIPV4AddressesFig.2.MethodstodetecttheclassofIPAddressTheFig.2clearlydepictsthat,firstfewbitsinbinarynotationofIPV4addressplaysavitalroleindetectingitsrespectiveclass.Asthefirstbit(MSB)ofClassAinBinarynotationis‘0’,wecansaythatitisthestringof32bits[actuallengthofIPV4address].AccordingtotheTheoryofAutomata,thelanguagefortheClassAaddressisdesignatedasL={0W|W∈(0+1)*}.Similarlythelanguageforrestoftheclassesisasfollows:LanguagetodetectClassBIPaddress:L={10W|W∈(0+1)*}LanguagetodetectClassCIPaddress:L={110W|W∈