gymtax Of high-level languages is defined with Comeary © these are used as a powerful too! by the ff Ere ser in verify Free Grammars, Hen Jevel language. ete ‘chapter, we will discuss (1) context free grammar, (2) ‘ derivation and (5) rightmost derivation, We aa eet ee ification of grammars and normal forms. also discuss ambiguous grammars, Context Free Grammars grammar, the productions are restricted n wo ways the et sie mus 0° wariable, while the right side can be any string of terminals and no terminals. To grammars that are very powerful, we must ease of Se ofthe estritions. By per anything on the eight, but retaining the retmstons ot the let side, we get cote context fee if all productions i P i: A grammar G 1, B.S) is said fo be Mtheform A> x where Ae Vandx € (\ uD. atialdesription ofa anes PeSarethefourimportant components inne : set of variables, also called non-terminals. ach variable th which it can be replaced. set of terminals, which is the set also called terminal symbols. finite set of productions oF 1 represents 261 oF SNES ‘of symbols that frm ime SE of the languse definition of the lt rl (9) and a st of f variable, pron a ys re at gent the anguae ‘being defi nt the stings of ogoxtions a8 SUNS 5 vv (CFL) Be ihatean be produced from Ine sate Sree aves \ crGiscalled® yge generated by #ree nel = anhea | then L =a boc Theory Automata gesand Formal Langu 150 productions: pee eeeia ean FESDIIED 1: ctr sings ith cay! mambo o The productions P are Ee 2 S— SaSBS, SbSaS |e And the grammar G = ({S}, {a,b}, B.S) eRe rete a erect cere sic corel baie expressions with the variables x, y Hete the grammar G = ({S,T}, (=, *, ( SoT+s To MTT |T ‘Ths grammar can generate the string (x +y)*x ~ zy |( + x) {a:b]) in which number of’ is different from the number of bs is Ssulv USPau|Tat Vorby|ror ToaPbT|bTatle yate-T can generate al strings in which number of as Sera tes with more as than be ent generate EXD 9 vccivireeon, Dns CFG for (O11 + 1 AS CAle Con)and b’. ) correct alge- I strings (over umber of bs, U ess a's than b's. ene Context Fee Grammars and Context Free L 151 oHOG CFGis eS CFG fo a saeice| the number of a's. [lion The given language is a° (bby. Hence it can be defined by S > aSbb | abb favbich first and last symbols differ. ‘Solution: The strings should start and er ‘auhave any string on 0(0 + 1)* Tie grammar is given by S04 A=O0A|1Ale = ‘ Derivation of CFGs Derive a‘ from by 2F Terminal: a fon for a isecono 100" 52 |_ Ferma! Lanquanes ar ‘utomata THeOTY gaas a > aanae = aaa “The language has the strings (E585 a2, 40% Terminal: Nonterminal: S Productions: S > SS 2. Soa soe We can dc Solution: Derivation of a can be achieved in many ways as shown. sss = Sa = aa (or) sass = sss = SSa = S8Sa > SaSa = exSa = eaea=aa EEN 6) an serve ine string abba fo the flowin Terminals: a, b Non-terminals: § Productions: Soas So bs Sa Sob Solution: Mote compact notation of the given ‘grammar is i S48 |05 [alo ean derive abba as fats: {aj Saas abs = abbs abbas,eT ENS wee A e Ta Tel > $.$0,b4, ! Cont ext Free Grammars and Contoyt Free Languages 790,65) 153 = abbab tor) cafe language generated by the grammar is (a py i Findithe language and derive abbaaba from the fol terminals: a, b i grammar: non-terminals: S, X productions: S$ XauX X > aX |bX\e Slaton: CFL is (a +b)*aata +b)* ‘Yeean derive abbaaba as follows: S= XaaX = aXaaX, = abXaaX = abbXaaX, = abbeaaX = abbaaX = abbaabX | = abbaabaX | = abbaabae = abbaaba 43 Understanding the Language Defined by | Grammars Titonly way to recognise the language isto try ou ‘Hebrules. Simply by observing the derived strings, fam the given CFG. @ {8osshS} ous strings from the he .d out the language cone can fin {S}, fal, s Solutio, at is derived from UG) = ©. Since there is no terminal that Give the language defined by gras G={15,C), fa, b), RS) where P is even”? S>aCagee caer oo ag ermal anquages and Automata T2O"Y =p aaCaa aay UG) = {erbat/ nz 1) EoD Give the lan Ga {iS} {0, UPS} where P is given by se defined by grammar s30si |e ost = 0011 LG)= {ort n= 0}, Solution: S => 0S' 4.3.1 Leftmost and Rightmost Derivations The Jefimost non-terminal in a working string is the first non-terminal that we encounter when we sean the string from left to right. For example, in the string bbabXbaY SbXbY, the lefimost non-terminal is X. Definition 2: IF word w is generated by a CFG by a certain derivation and at each step in the derivation, a rule of production is applied to the leftmost non-terminal in the working sting, then tis derivation is called a lefimost derivation (LMD), Practically whenever we replace the leftmost variable first in a string, then resulting sation is called the lefmost derivation. Similarly, replacing the rightmost variable first at every step gives the rightmost derivation RMD. EEE) conser ne cr 15, x), (0,0. 5) where productions are S— baXas | ab X— Xab jaa Find LMD and RMD for sting w = baaaababaab, Solution: The following isa LMD, SS ees las Ss baxas} =a abaS {88 X > Xabj 3 kababas fas X — xab} = basanghesy (28% > aa) The following isa RMD.» 8 Sab) S=baXaS fags, = buXsad fas § oa = baXabsab — as X > Xap) = baXababaab {as x 5 Xib} = baaaababaab {as X — aay ‘Any word that ean Pe eenerated by a given CFG can have LM DIRMD. ice followir s AB2 D The derivat from a CFG show us cle Which belor For cons Toot is each nc each in ifan in left, theGe COs * hd iad | wey" Lx aaa, bbb ccc @ core teh eri wey Sty Te, Context Free Grammars and Context Fre Larquages om Consider the CFG: $9 aB |bA A alas |bAA | | 155 Bb/bSjaBB [uiDand RMD for (the string) w = aabbabba lowing is a LMD: = aabbAB aabbaB = aabbabS = aabbabbA _ on-terminal is X. = aabbabba f jerminal that we encounter rivation and at each step in on-terminal in the working ). 'in a string, then resulting ng the rightmost variable pine isa RMD: S>aB => aaBB = aaBbS => aaBbbA. = aaBbbal = aabSbba = aabbAbba = aabbabba 4&2 Derivation Tree nine | Theésrvation process ean be shown pictorally a5 ie i ation ees TH 7 oma CFG, These trees are called syntax tees, Patse EES NTT cuhstrings eat of SW Us clearly how the symbols of the terminal STB A ay hich belongs to the language of one of the vars Foreonstructing a parse tree for a grammar O= Bi al or €. 4 Sath node lubeled by either a variable, «terms Metric iernarkedby variable MV ax. B itah interior node is labeled A, and its children then A X,, X,,.. « X, isa production” Xp from the: ample 4,18 Wega ‘Terminals: a, b u Non-terminals: S.aaa ege + EL pa faalalelolole lel Theory id Automata yanquges a 196 | Feral tion S > AAA [AA aon jr AA 0A Aba |e derivation tree; as shown in Fig string “baaba’ i Fig. 4.1. Derivation Tee for “baaba’ € gel a string, which When we concatenate the leaves of any parse tree from the lef, we get a string M xuown as yield of the tree, The yield isa string that is always derived from the root var ah There are parse tees whose yields are inthe language of the underyin importance of tree is: immar. The 2 Theil terminal sting, All eaves are labeled witha terminal or a 3 The root is labeled by start symbol 2 At any intermediate ste tential form, >. Pe concatenate the clements, we get a string inthe sen- 4.3.3 Equivalence of Parse Trees and Derivations Toccata inthe language oF grammar sthe yield ere son ieganimar itis the yield of atleast one parse ee ett vain ign sense ete sare equvalxn “Wit so th sins excl the seine cI nh ngs in the language of a CFG vce aie CFs, tray be posts aon {erminal string with more than one parse Shapley: with more han one left Aerivation oF one rightmost derivation Stcha grammars called ambiguong 4.4 Ambiguous Gr. ammar string id 4wwe get a string, which ved from the root vari derlying grammar. The pinal ora € get a string in the ser tions rat least one parse tree trees are equivalent, FG. th more than one P: ¢ rightmost derivation tree, or re than one * Context Free Grammars and Conte Fee Languages | 187 GRAMMAR F Unam ambiguous era aaa. pecexiss more than_ane LMD or RMD. Unique MD) RMD feasting MDa RMDrenrssens dilfrentparse LMDA& RMD repens sane ees parse tee ior than one parse ree fora'sting Unique pase ee FEED svar Eid) E+E [B*E[E-E smmat is ambiguous Soluion: UMD: for string id + id*id, the derivation is ESE+E Sid+E Sid id tid Stagid = id* i, can also be derived as SEtE SE+EtE EE cen Bee Parse trees represented by the above derivation is shown 1" Figure 4.2; : * : MB eT > j id ie id id ; ria.a2 pao Teor 1! Noe ambiguous Here more than one parse te, he grams SNee prada - words Languages and Automata THe 58 | Formal poo Consider the Grammar G with terminals: b ron-terminals: S productions: S— aS | Sa|a Show that G is ambiguous. s s _ Ai fo : i Fig. 4.3 Parse Tree for ‘aa’ Solution: The word aa can be generated by two different trees as shown in the Figure 4.3 Therefore, grammar G is ambiguous. ELSIE onic Grammar o win terminals: a, b non-terminals: S productions: S => % S | aSb | X X— Xala Show that Gis ambiguous. Solution: The word “aa” X= Xa aa S>aS aX aa i ST Solution: The 2 s which has deriv Since there i | Example 4. Solution: To ch This has tw Since there are 4.4.1 Ren There is no al “nambiguous g Brammar and w For example Tire take a str ifwe ana-orrespond to the following mo > aX = aa s Tree for “aa (the grammarisambié © consider ee rae ee 4, 22 80b) aD @- 140,03 oe. MO a) 2 Tob PS Context Free Grammar Context Fee Languages | 159 Soltion: The grammar ean generate the string “babbab’as follows S580 = bas = babSbab = babbab hiss derivation tree shown inthe Figure 45 Sines theres only one parse ee, the grammar is unambiguous FEI recites towing grammars ambi oa Soicis|iceSesia Cb Sion: To check the ambiguities consider stable input string, Let string be “ibaa” Thistas two derivation tees shown in the Figure 46 ae i a as, Fig. 6 Te for ibbaea” ‘es there are two possible parse trees the grant fs ambiguous 44.1 Removing Ambiguity Thee 350 algorithm that straightaway converts an ambiguous grammar 1 equivalent SEznbigsous grammar But on analysing the gamma e ent) whats mising nthe ‘eninarand vty is unambiguous then we can weteequvalent unambiguous grammars, example, consider expression yrainar given blow Expr» Expr + Expr | Expr * Expe|id id rid sid + id we got 160 parse trees zammar with the above two igs, We understand the following lee Uokea string ia he String —_—_sfapo)opslcie"l Le |e ~ of Read (ort eat Inthe given grammar, + thats, A Aa] b The equ Tote |r 4.5.1 Elir Foid This procedure can be used for any expression grammar. Definition 4: | aro ‘gui To check i 442 Inherent Ambiguity or by using th Silt be inherently ambiguous i cmambiguous 4 Lemma 1: If gus language lent grammar Letebedliqjk=1) ae: SAB|C Proof if A — A= aAb ab Production wi | B cBd ied following alge © C4 aba D = De be i Include Repeat s r= Vi Me Vey. From the a Melude V4ee ie Te 162 | Formal Languages a » ABa| BC, A > aC| BCC, Ca, B = bec, DIE,E>dFe symbols: All variables are found mn of non-reachable i © ©-6 © F047 Graph Representation tp Iden 9 DE and F are no © Afier removing u uity Useless Non Terminals mn-reachable from scle3s sym sol ter? Soluro ~ ges and Automata Theory 464 | Formal Langue proce a For where §, € tions aS S-ABAC | BaC | Aa | Al ASBC|BIC Bob csp - Do4 | E=2 ASBB ! Bobb |e | SsaAla 22 BBB | Babb jay 45.3 Eliminatin 9 Uni Pefiniton $n t Prod Foduction Uctions,~e pn Telet> peer? Talalelb CIC IC/R } Q” pelelelePlee Ee gis Bee febhs as pie: oi} Readfunite | BG b= EB ly wa | ob) - 10,89 2 operation of TH ON Th w3A% Context Free Grammars and Context ree Languages | 165) z rocetr or Eliminating Unt Productions Sing Gy rarGachpalcoFortervinalsA and B sch hat there isa production emg Pe auch onintrrecuctens : er tag BEST 5-15, Je the new produc A-5)]8]..-15, Do the same forall such pairs A and B simultaneously Remove all unit productions. SSA bb A>B|b grammar fee + Afier eliminating unit productions S > A, AB, B—> Swe get Sa\b|bb,A>alb|bb, B—>a/b|bb 5 Aa|B,B>A|bb,A—albe|B Solution: Unit produetions are S > 8, B > A and A> B — A,B and S are derivable Fliminating B in the A production gives A abe |b. Eliminating A in the B production gives B— a | be | Bb = Ftiminating B in the $ production gives S >» Aa|a|be| Pb 4 The final set of productions after eliminating unit productions are given Delow S$ Aalal be | bb ae B—albe| bb ge A—albe|bb EXEIZEDD sini ne owing sama $s aA]aB8 AaAALe B+ bB | bbc C58 Solutions vere tis beter 'o eliminate null productions 2s may inroduee usless sym baad Uterus Next cliinatuniproguton anda the nd fiminat sles symbols Removing e- productions gives resulting grammar as Saha [238 sal ASadalaa|a8 (%,b) =o, 9 (to, B) ~ 12,8 The ofevatiog es Po omata Theory 166 | Formal Languages ana to sai Ss aA|a|aBB Po jn the Follo B > bB | bbc Cb OC pols, Eliminating these, we B and C ae identified as useless symbols. Eli Saale A >aAA aA [a Finals the reduced grammar is) aA |a, A> aAA |aA |a which defines any number ae ‘The lan original C Eo 4.6 Normal Forms As ne hav sen, the grammar canbe simplified by reducing the € productions, emoving bath usless symbols and unit productions. There is also a need to have the grammar in specific form. AS you have seen in CFG, on the right-hand side of production, there ay number of terminals and non: minal, in ny combination. We need to normative sich a grammar.to standardise the processing of strings Thal means we wnt the insome specific format There shoud be a ftned number of erminel, oy non in context fee grammar with some criteria, Thee are tr Solution: Ther Faas Nomal Form andthe Grebach Normal Form, We wil study thers two normal A>a,Bob forms wth help of examples. important normal forms: The Other produ 46.1 The Chomsky Normal Form Dehation6:& CPG sin Chomsky Norma often, 281 Chomsky Noma Form (CF exch oft potions hs om 1. Non-terminal ~ string of es i. ! Siting of exactly two. Non-terminals, ie., A > BC ion. 2 Nontermin one terminal ieee production 4 InCNF number of symbol one tat of symbol i hhand side of production is strictly limited. The ie is also restricted the right-hand si Mocs or Converting a ven Gr 1 immar to one productions and unit lutions ofthe liminate nu Productions, oon BC lla asin ls on the tight, HeFigh-hand side of production i they exceed one HPoHE We have the production This is the C xn 4,4, are terminals ac Cara,a — Fis eRaeye rts Ss ~ J (ab) f Lo, PS i Read unite : 7 P ’ I $408) ~ 14,84 The operation of TM OF one Free Grammars and Context ree Languages | 167 4 Toei hs mb farses on he right-hand i, ntoduce new var Sarpose we Fave the production wih © sondsrminals as shown bow wih 5 YOX,X,X,x,x A n2 ne production singh? ney nonsense the prodtona YoXR ROXR defines ‘ R,>X,R ROXX where the R, ar original CFG. “ f production. SbA|aB wed ton A—bAA|aS|a we wat Babb bs |b als oF ne aan Solution: There ae no nul or unit proutions. x iy A > 2.B bare in the required format, so they are staightavay included, Other productions are notin CNF. So, replace every terminal by the following variables S3GAICB A>GAAICS|a BOC_BBIC,S|b Cag ob ‘ fis A GAA and B + C, BB are the only two productions that are notin CNF. So aud ‘foe on-terminals D and E, one fr the first production and the oer forthe second *odiction. And add two new productions as follows: S>GA/CB A>CDICS|a B-C,EIC,S|b C7a.C,3b DAA Es Thisis the CN se SAB aB A->aab|e Bo bba468 | Formal Languages and Automata THEO" productions S$ AB/B|aB A-aab BbbA [bb Solution: Eliminate Eliminate unit productions SAB |bbA | aB | bb A= mab BbbA [bb Replace the terminal by a variable $->AB|C,6, A/C, BIC, ACCC, BIC.GATC,< Cac Restrict 10 to yariables on the righthand side of each production SAB] C,D|C,BIC,, ACE BIGDIC,c, C765, DaGA, Ecc, This isthe required CNF FEED coven stoning C2019 cE SASB |e,A aAS|a,B > SbS/A/ bb Solution: Step 1: Simplify the grammar with productions P. Step Ta: Elis Piis S>AsB/AB AS aAS|ajaa BSb5| A bb| Sb |6s)b Step Ib: Eliminate unit Pris inate e-productions to obtain P, Productions to obtain P, S>ASBja0 ASaks lana 8848/8 (9b 68 basa) Sept: Emit use lee 818 Alll variables are ni f Simp rma Wand all are reachable, =(1S,A,B}, {a,b}, SS ASB AB, A aAS|ajaa 5 SbS |b/ Sb bs |] PS) where P is AS} a] aa step 2 step 21 Add pr Step 2c required Adding © The ty Oo Pritext Fre Grammars and Context Fee Languages | 169 Pris SAB step 2b: Eliminate terminals ftom RHS of he other production AeA 3 ASCA BSUS > B>SCSandC,>b Bobb > B3C¢ Bobs SBCs ction B+sb > Bost Ad productions that are in CNF form t SoA BIGCIES|SCICA|> Step 2c: Reduce the RHS of the remaining productions with more than 2 variables tothe S> ASB SAC, and C, > SB Ajbb ASCAS= ACC, and CAS BSCS BSC, and C, >. B4CAS=>B>C,C,andC, + AS Adding these productions to P”: the complete grammar is S>AB|AC, A>alCAlCK BICGIGSISGICA|SCICC|b]8 ©, 44,6, 98,6, 9 A8,C, 9GS,C, AS. Ps) rammar in CNF form G" = (V", (a, S.A.B,C,.C.C, CC) SACJAB Asalcalce, BGG, [CS] SC, |C,4|SC, |CC, |b] 2 ©, C9b,C, + AS,C, 9G, C, 9AS,C, 9 SBwan enn a0 | roma anqiages ane furmata TOY 4.6.2 The Greibach Normal Form ction not onl put restriction no i the postions at which ter™ tenatty of ight sides of production but also in conn- and variables an appeat zach normal form if all pro- lyon the Here, wep cation with) rina rissa wo be anthe Ore smext foe langue is : Aconex ea wereae Tard 3 V | a grammar to GNF GNF, we se two Temes Definition 7 Ba|Ba1B, 418, Lemma 2 (Elimination of left recursion) Grammar of the form A > A. | B is called left-recurstve grammar. To eliminate left recursion, rewrite grammar as ASBAY Aaa’ |e. Ife eliminate production, we Est ASB BA’ Aa AY ‘We can generalize tis grammar. For any CFG given as A> Aa,|Aa,|Acy....|,\B.1B,| ‘he equivalent grammar aftr eliminating le recursion is A B)A/B,81B,4"|...../B,| B,1B,) A’ >a, A’|a,A’\a, A/).....|1a,\a,) 0, Procedure to Convert the given Grammar to GNF 1. Eliminate null produc i is ate null productions and unit productions, and construct CNF. foname variables a8 AA... starting with Sas A, 3, Foreach production ofthe form 2) joi form A, A,o, apply the following: 4, For each production of the form, A.isinGNFtobringA,toGNE | EEEIIZED oomericcrcmone S>AAla ASSS|b ‘Solution: Rename variables by S=A\A=A, APE ADI nor con Sol Ste Ste Ste Ap Sub Noywaa jon, but also in conn- sanal form if all pro- ‘there is @ production ned by substituting B mar, To eliminate left ct CNE. m8 ly substitution lemma if (eB) IH 5 9 Context Free Grammars and Context Free Languages | 171 A, PA,All en -(l) AAA |B 2) Apply Lemma | for (2) A, A,A,A,|0A,|b ply Lemma 2 for this A,-aA,|b|aA, Z| bz ZA,A,|A;A, Z substitute for A, now in Z Zoah,A,|DA,|2A,A,ZIDA,Z|aA,ZA,Z|aA, ZA BZA, DZA,Z Aah, blaA,Z|bz A, a]aA,A,|DA,|aA,ZA,|bZA, Forany CFL L, the non-e words of L can be generated by @ CFG in GNF. Greibach ‘pomial form is usefll for proving the equivalence of CFGs and NPDAs. When we discuss converting a CFG to an NPDA, or vice versa, we will use the Greibach normal form, S> XA|BB B>b|SB X>b A>a Solution: Step I: Rewrite G in CNF. Itis already in CNF form. Step 2: Re-label the variables: Swith A, Xwith A, Awith A; Bwith A, ALS A,A\AA, - ay BeDel asa, Q) Ab e) Ama (4) Step 3: Identify all productions that do not conform to GNF. Apply Lemma 1 for (2): AOA AAIAAALLD Stbstitute a, — p : k A, ObA,A,IAVAALID ™ 4Pply Lemma 2 on A, > A,A,A, A, >bA,A,|B1DAAZ [02 ZOAASAAZes and Automata Theory 472 | Formal Languan ow the resulting grammar Is AAA AVAL Alo bA, A | b| DAA. Z |b2 ZA A IAAZ Ab Step & Ni Aa ot in GNF Still dhe grammar is not in ( s: All productions A, Ay, A,are in GNF But A, and Z are not in GNF Step & All productions Ay, Ay Ay ForA, 3A, Ay/AVAy Suibsttute for A,and A, to convert it into GNF A. SbA,|DAA,A,|BAIBAA, ZA, | BZA, For Z9A,A,|AAZ Substitute for A,to convert it into GNE ZDbAAA,|DA | BAY BAZ|BAAZA,Z|bZA,Z A,[bZA,|DAAAZ Step 6: Final grammar is A bA,|bA,A,A,|bA,|bA,A,ZA, |bZA, A, > BA, A,|b| DAA, Z [bz Z—DA,A,A,|DA,|DA,A,ZA, | bZA,| A, A,A,Z. |DA,Z|DA,A,ZA, Z|bZA, Z Aob Asa EEE Convert the CFG to GNF SABA Aadle BbBle Solution: Eliminate ¢-productions SABA|AB|AA|A|B AsaAla Bo bB|b Fliminate unit productions SABA |AB|AA aAla AnraAla mee BbB\b Now substitute for A and B in S SaABA|a, ‘AT#AB|BBA|aAA [aA || BB |b] aBA | aB | aA |bA A-aAla BobB\b This isin GNE 4.7 The pt set cor and if regular that ar 4.7.1 LetLt such th Proof: and wit context For the from ro is less t Basis: Let ¢ accordit word wh Hence,Context Free Grammars and Content Fee Languages | 173 4,7 Pumping Lemma for cFL fhe punping lemma for regular ses sates sci a hr ssn tat ean be puna en wie pas or pump ay number onc teu se Accoring fo pumping leona ne tata cose fo cachother and hese uber that every sufficiently long string in a regular ‘a long string is given ‘ny number of times, we always get a there are always two short substrings can be repeated as many times as required 47.1 Lemma Let be any context free language. Then there isa const fant, which depends only upon L such that here exists a string 2 © L and le|>n, wh H i. ere Z = uvway such that L pale 2, |ywx) Sn and 3. Forall 12 0.uviwe'y isin L. Sets fem states that, in aTanguage L that is without unit prodetions ee ee cians there exists a zyhere ze L, The string z-can be derived bre soni Tes grammar G. Let G be a grammar and let it bein the Chomsky normal org facie Seine z Wwe can obtain a parse tree that derives the string z. The depth ofthe path Fesmroot to the leaf node for the yield zis less than or equal toi, then length of the veel 5 isless than or equal to 2. We can prove this by induction, Basis: Ifi= 1 PetG contain the rules S — a where length of the derived string is I, ie i= 1. Now Sseording to the rule, the word length should be < 2~! = 2" = |. Observe that we have g [isiwhhich is of length 1. Also observe that the grammar G is in Chomsky’s normal form, Hence, the language is regular since |2| = juvwx3 Fig. 4.8 Tree with Three Distinct Non Terminals and with String Length 3 Pisin sep: ctw bea string that is derived by grammar. Let Hee nha Gl]; then [a > 2’, when deriving the string w we may get some non-terminals Beebe repeated any number oftimcso give the string zs shown inthe Figure 4.8 mt the substrings to w such that the pathlength ofits newly formed Sora: Fie, 87is iand the word length of’ is 2, then the grammar G defying z Wink tel erammar. The necessary condition is that grammar G is in Chomsky’s normal form, Pex te lowe cece ion Ba G=(1A, B,C}, fa}, {A > BC/a, B > BA|b,C > BA}, A)4174. | Formal Languages and Automata Theory Thus A> bbi that is, path Tength 2-1 that is, 3 <2 iw 2/1 AB, A — BB, B-> AS |ais finite? suered about the context The directed graph for the given grammar is shown in Figure 4.10;Context Free Grammars and Context Free Languages | 179 4 aaaaa is not accepted as the The given sti nents in V,, do not contain the start y symbol: rom the table, we can say that aaa or aaaaa strings are accepted, 410 Closure Properties of CFLs (CFLs are closed under substitution, union, concatenation, closure and positive closure reversal homomorphism, and inverse homomorphism. BiH =v.n te [CFLsare no closed under intersection, difference and complement : ; 2) CFLs are closed under union F sbi Theorem 1:1, and L, are CFLs, then their union L, Lisa CEL oe Le the grammar CFG, define the language L, Assume that the non-terminals in if ae CFG, are S,, A,, B,, C,...... Let L,be a language defined by CFG, and let its non: Pt ALN AISAC terminalsbe'S, A, B,C, pe < Now CFG, and CFG, have non-interscetng sets of non-terminal Fg 01th Wecreate a CFG for L, + Ls follows SAC) Include all ofthe non-terminals §,, A, B,, C,--and S.A, B,C SAG) 2¥,=15,4,C Include all ofthe productions from CFG, and CF, ge = Greate anew nor-terminal Sand a new production in CFG s BA 6) 55,8 x ~~ 18) This production takes care of generating all the tings xe L(G,) or L(G.) as (S) | $a5 54 ifne La) 6) » JPFLS are closed under concatenation oe Maem 2: 161, and L, are CFLs, then L, aclxj automata TeOry 480 | Formal Languages a Assume that the non-terminals in ofthe word is art id by CFG, and let its non. that come before i CEG, define the language L, Lettie grammar CFO, ie Ee CA, BG ve etl oe Seer scting sets of non-terminals. We create es : CFG, and CFG, have non intersecting set ows! ea arin Is SpAp By Cer and Sy Ay» Ba Cp Jude all the non-terminal 2 sductions from CFG, and CFG, 1 production: Ire Thus, L, = {a a clump of b’, anc middle is the same of the word is arbit where x € L(G.) with S, = x and y © L(G,) with iieticonielaficnil Note that L, 9 L free language, as pi Include all the pro a new non-terminal Sand es rules ean derive S => xy closure under intersection ©) CFLsare closed Theorem3:IFL isa CFL, then L* is a CFL + Since Lisa CFL, by definition, theres some CFG that generates L. Suppose CFG ©) CFLs are not closed for has non-erminals S,A, B,C... Change the non-terminal Sto S,, We create Theorem 5: Let L be anew CFG for L as follows: We first assume that Include all the non-terminals S,,A, B,C, ... from the CFG for L. iaaieeeeuier, then Include al of the productions from the CPG for L We now show that th Add the new non-terminal S and the new production Ee ist itis SS S|e are CFLs, then by ou We can repeat last production: that L, +L, isa CFL +L,)isa CFL. But w Seo S585 Lash However we ote that any word in L* can be generated by the new CFG. To show that any word 4 CFL, which contra senerated by the new CFG isin L*, note that each S, above generates a word in L always closed under ¢ Also there sno interaction between different, , : S458 88S 9558555558 4555, Thus, in general, it is 4) CFLsare not closed under intersection Theorem 4 Let L, and L, means they are not clo be woCFLs then, 1, may or may not bea CF. Ths 4 ms sciunier intention M1 Applications We now give an exam 5 coz St an example sowinghat he nrseton of wo CFLS may not 8 © Grammars are use in Fein tis assure that he language L,=(ahb' n> 1} isnot a cortex ™ainly used inthe desi guage. L, is He set of words with some number of 2 They are *) a’s, followed by an equal d they are ending with the same number of a's, 4 Let, be generated by te following CRG also used in na 8 Tami mil poetry called Vey meas henumber of) nthe midi, The nner of asa hs Sime . ©Ptional_stmts — fisvith CFG ny word yd in L. y not be 2 {a context y an equal are followed of as at the ra’s atthe end Context Free Grammars and Context Free Languages | 181 sine word sabia ar! doesnot have tobe equal wih the numberof a and BS that come before it. tert be gonerated by the following CFG s3wz WoaW|e Z>bza\e Tus, Ly = {b's k= 0}. Words in tis set havea lump of as are followed by elump of DS, and are ending with another clump of a's. The number of BS in the ride isthe same as the number of asatthe end. The number of a's atthe beginning, Miike word is arbitrary, and does not have to be equal with the number of bs und as that come after it Note that L, 0 L,=Ly where L, = {a"b'a":n=0, 1,2, J, which is nota context Fiee language, as proved by pumping lemma of CFLS. Hence CFLS are not closed ‘under intersection ¢) CFs are not closed under complement ‘Theorem 5: Let L be a CFL then L- may or may not be a CFL ‘We first assume that the complement of'a CFL may be a CFL, TPL is regular, then [is also regular. Also both Land 1. are CFLs: We now show that the complement of a CFL may not be a CFL (by contradiction) Suppose that itis always true that if. is a CFL, then Tis CFL. Let L, and Le eCFLs, then by our assumption, L, and L, are CFLs. Closure under union implies that, +[, isa CFL. Then by ourassumption, we must have that complement of ( I +1.) is CEL. But we know that complement of C+ L, L, by DeMorgan’s Lad, However, we previously showed that the intersection of two CFLs is nok aways SCHL, which contradicts the previous two steps. So our assumption that CFLs are always closed under complementation must not be true aCFL is CFL Thus, in general, it is not true that complement of 411 Applications of CFG 3 Grammars are useful in specifying the syntax of programming languages mainly used in the design of programming languages 8 They are also used in natural language processing, 8 Tamil poctry called Venpa is described by a context fr «also in processing s They are grammar 4 CFGs are used in speech recognition an poken words 5 The expressive power of CFG is too limited to adequately capt itrncna, Therefore, extensions of CFGs arc of interest in computational Unguistics EESIZET) san example, CFG for pascal statements are ziven below. aa > begin optional__stmts end ©ptional_stmts > list of stmt | € jure all natural language