Formal Grammars and Languages

1 FormalGrammarsandLanguagesTao JiangDepartment of ComputerScienceMcMasterUniversityHamilto n,OntarioL8S4K1,CanadaMingLiDepartment of ComputerScienceUniversity of WaterlooWaterloo, OntarioN2L3G1,CanadaBalaRavikumarDepartm ent of ComputerScienceUniversity of Rhode IslandKingston,RI 02881,USAK ennethW. ReganDepartment of ComputerScienceStateUniversity of NewYork at Bu aloBu alo,NY 14260,USA1 IntroductionFormallanguagetheoryas a disciplineis generallyregardedas growingfromthe work of linguistNoamChomskyin the 1950s,whenhe attemptedto give a precisecharacterizationof the structureof goalwas to de nethe syntax of languagesusingsimpleand was foundthatthe syntax of programminglanguagescan be described usingone of Chomsky'sgrammaticalmodels earlier.

2 The NorwegianmathematicianAxelThue studiedsequencesof binarysymbols subject to interestingmathematicalproperties,such as not havingthe samesubstringthreetimesin a row. His work in uencedEmilPost, StephenKleene,and othersto studythe mathematicalpropertiesof stringsand collectionsof afterthe advent of modernelectroniccomputers,peoplerealized thatall formsofinformation|whethernumbers, names,pictures,or soundwaves|canbe represented as stringsknown aslanguagesbecamecentralto concernedwithfundamental mathematicalpropertiesof languagesand languagegeneratingsystems,such as programminglanguagefromFortranto Java can be precisely1described by a.

3 The grammarallows us to writea computerprogram(calledthesyntaxanalyzeri n a compiler)to determinewhethera stringof statements is syntacticallycorrectinthe peoplewouldwishthatnaturallanguagessuch as Englishcouldbe analyzedas precisely, thatwe couldwritecomputerprogramsto tell which Englishsentencesare advancesinnatural languageprocessing, many of whichhave been spurredby formalgrammarsand othertheoreticaltools, today's commercialproductsfor grammarand style fall well shortof thatthere is no commonagreementon whatare grammaticallycorrect(English)sentences.

4 Nor has anyone yet been abletoo era grammarpreciseenoughto propose as de nitive. Andstyle is a matterof taste!such as notbeginningsentenceswith\and"or many applicationsin other elds,includingmolecularbiology(see [Searls,1993]) and symbolicdynamics(see[Lindand Marcus,1995]).In thischapter,we will present someformalsystemsthatde nefamiliesof formallanguagesarisingin many primaryfocus will be on context-freelanguages,sincetheyare mostwidelyusedto describe the syntax of the rest ofthis section,we present somebasicde nitionsand a nitenonempty set ofsymbols.

5 Symbols are assumedto example,an alphabet for Englishcan consistof as few as the 26 lower-caselettersa; b; : : : ; z,addingsomepunctuationsymbols if sentencesratherthansinglewordswill be it mayincludeall of the symbols on a standardNorthAmericantypewriter,which togetherwithterminalcontrol codes yieldsthe 128-symbol ASCII alphabet, in which much of the world'scommunicationtakes an alphabet calledUNICODE, which is intendedtoprovidesymbols for all the world'slanguages|asof thiswriting,over 38,000symbols have aspectsof formallanguagescan be modeledusingthe simpletwo-letteralphabetf0.

6 1g, over which ASCII andUNICODEare encoded to usuallyuse the symbol to denotean an alphabet is a nitesequenceof symbols of .2 Thenumber of symbols in a stringxis calleditslength, denotedbyjxj. It is convenient tointroducea notation for the empty string,which containsno symbols at all. Thelengthof is anandy=b1b2 bmbe two , denotedbyxy, is the stringa1a2 anb1b2 any stringx, x=x =x. For any stringxand integern 0, we usexnto denotethe stringformedby of all stringsover an alphabet is denotedby , andthe set of allnonempty stringsover is denotedby +.

7 Theempty set of stringsis denotedby;. any alphabet , alanguageover is a set of stringsover . Themembersof a languageare alsocalledthewordsof the ;11;0110gandL2=f0n1njn 0gare two languagesover thebinaryalphabetf0; threewords,whileL2is in is in both languageswhile11 is inL1but not justsets,standardset operationssuch as union,intersection,andcom-plementationap plyto is usefulto introducetwo moreoperationsfor Languages :concatenationandKleene two languagesover . The concatenationofL1andL2, denotedbyL1L2, is the languagefxyjx2L1; a languageover.

8 De neL0=f gandLi=LLi 1fori 1. TheKleene closureofL, denotedbyL , is the languageL =[i 0Li:ThepositiveclosureofL, denotedbyL+, is the languageL+=[i 1Li:3In otherwords,the Kleeneclosureof a languageLconsistsof all stringsthatcanbeformedby concatenatingzeroor morewordsfromL. For example,ifL=f0;01g, thenLL=f00;001;010;0101g, andL comprisesall binarystringsin which every 1 is precededbya 0. Notethatconcatenatingzerowordsalways gives the empty string,and thata stringwithno1s in it still makes the conditionon \every 1" +has the meaning\concatenateoneor morewordsfromL," and satis esthe propertiesL =L+[f gandL+=LL.]]]

9 Furthermore,for anylanguageL,L always contains , andL+contains if and onlyifLdoes. Alsonotethat is infact the Kleeneclosureof the alphabet when is viewed as a languageof wordsof length1, and +is just the positive closureof .2 Representationof LanguagesIn generala languageover an alphabet is a subsetof . How can we describe a languagerigorouslyso thatwe know whethera given stringbelongsto the languageor not?As shown , a nitelanguagesuch asL1can be explicitlyde nedby enumeratingits in nitelanguagesuch asL2cannotbe exhaustively enumerated,but in the caseofL2we wereableto give a simplerulecharacterizingall of its members.

10 In English,the ruleis, \somenumberof 0s followed by an equalnumber of 1s."Canwe ndsystematicmethods for de ningrulesthatcharacterizea wideclassof Languages ?In the followingwe willintroducethreesuch methods:regularexpressions,patternsystem s, andgrammars. Interestingly, onlythe last is capableof specifyingthe simplerule forL2, althoughthe rsttwo work for many languagesthatcan be described by a body of LanguagesLet be an and the languagestheyrepresent are de nedinductively as Thesymbol;is a regularexpression,and represents the empty Thesymbol is a regularexpression,and represents the languagewhoseonlymember is theempty string,namelyf For eachc2 ,cis a regularexpression,and represents the languagefcg, whoseonlymemberis the stringconsistingof the Ifrandsare regularexpressionsrepresentingthe languagesRandS, then(r+s), (rs) and(r ) are regularexpressionsthatrepresent the languagesR[S,RS, andR , example,((0(0+ 1) ) + ((0 + 1) 0)) is a regularexpressionoverf0.]