Unit HI jON OF CONTEXT FREE (N, T, P, S) be a CFG. The language of G, d as L(G) is defined as the set of terminal strings have derivations from the start symbol. UG) = fais 2 | G language L of a context free grammar G is called as ; Free Language (CFL). ‘example, let G = (N, T, P, S) with N = {S) T=(0, lhandP={Se S30 Soi soso So1s1 } is @ grammar that generate the palindromes. er L(G) which is the set of all palindromes over is a palindrome then only (G) and if w is a palindrome then w = w* sider the length = 0 and 1 as a base condition. If S—>Oand Sal ‘we can conclude that S > w. ‘consider |w| 2 2. As w = w* w must begin and end terminal. =0x0or CONTEXT FREE LANGUAGES (CFL) Assume that x € L(G) ie sax Consider w = 0x0 $050 0x0 = w Consider w = [x] As Sx Ss] kl=w UO). wis The three major classes of languages are CFls, regular sets and the recursively enumerable languages. In this section we shall see the grammatical definitions of the regular sets and the regular languages. We have already seen the four classes of languages given by Noam Chomsky. 1. Right Linear If all productions of a CFG are of the form A + w8 or A> w where A,B N (variables) and w is a string of terminals (possibly ¢), then we say that the grammar is right linear. 2. Left Linear If all the productions are the form A > Bw or A> w, the grammar is left linear. A right linear or left linear grammar is called as a regular grammar. For example, the language 0(10)* is generated by the right linear grammar. S+0A A> 10A/€ The corresponding left inear grammar is S>S10]0 2.2 Regular Grammar and Finite Automata Regular grammar characterize the regular sets, in the sense that a language is regular if and only if it has a left linear ‘grammar and if and only if it has a right linear grammar. 2)THEORY OF COMPUTATION (COMP., BATU) 32) ‘Theorem : If L has a regular grammar then L is a regular set. Theorem : If Lis a regular set, then L is generated by some left linear grammar and by some right linear grammar. The class of languages generated and accepted by the FA is called as regular languages. Lets see the construction of regular grammar from given FA and vice versa. 3.2.3 Construction of Regular. Grammar for a Given FA + Lets assume that there is a DFA M, with M = (Q, 3, 8 pF) with Q= {G0 Ga, -. Gel- + To construct the equivalent grammar G, the productions of G are mapped to the transitions in the DFA. When a final step is reached, the derivation should also terminate. The equivalent grammar G is given by - G = INTP,S} = (Po Ayn Add where ‘set of productions P is constructed as aA, is included in P if 5(q, a) and A; — a are included in P if 5 (qi a) qand qe F. points to note here are will have ‘n' variables if there are ‘n’ DFA, state of DFA, then the starting non- sponding to qy will be the start tions in the DFA, there are ‘m’ Grammar G. - is as shown in Fig. 3.1, CONTEXT FREE LANGUAGES The equivalent grammar G is given by ~ G=(NTP,S) N = (Ao, Ax, Aa} T= {a,b} and Ag is start symbol. P= (Ao ah, Ag? bAg Ay ahsla Ay BAL Aa ahs A,>bA|b } 3.2.4 Construction of FA from a Given Right Linea, Grammar Consider G = (Aa At wu An), E P, Aa) is a right lines grammar. Let the corresponding DFA M = {(qo du «= dy q) 2, 5,a0 (ah The resultant DFA has ~ The states corresponding to the variables. Initial state corresponds to Ap. The transitions correspond to productions P. The last production applied in any derivation is of the form A, -> a, the corresponding transition terminates at a new state and this is the unique final state. The 6 transitions of the DFA are defined as (@ Each production A, > aA, produces a transition from q, to qj by input a, (b) Each production A, — a produces a transition from 4 to gy with label a. wn Note : The resultant FA is NFA which can be further converted to DFA. Example 3.1 : G is @ grammar with productions S—aA|bB AsaSla B>bS|b Solution : Seao Acoa Bog The corresponding FA be M = (Q, E, 8, qo F) with » Q= a qu qq) F = {qd E= (a,b)example, the productions of Ge are: S>bB Bo bc Baap Coa Bob Corresponding transition graph is given by. CONTEXT FREE LANGUAGES (CFL) Here our assumption is that if a production leads to a terminal, we reach to a state labelled as *. To obtain the equivalent left linear grammar interchange symbols “ and S and reverse the arrows. The new transition graph is given on the next page. The production rules of G; are given by ~ S3Ca SBb C38b Bo Ba Bob Fig. 3.4 (2) G toG: We can find the right linear regular grammar from a given left linear grammar using the same procedure as discussed above. Let the productions of G, are S— Cal Bb C38b B—Balb The transition graph for productions of G; is — Reversing the graph arows and inerehanging "2 . J Productions of Gp are - SsbB BB Bb B— bc ca Fig. 3.5THEORY OF COMPUTATION (COMP., BATU) © Ta construct the FA equivalent to a left linear grammar follow the following steps 1. Let G = (N, T, P, S) be the left linear grammar. Obtain a right linear grammar. G' = (N,T, P'S) where P*is set of productions from. G with reverse direction productions. 2. Construct FA from G’ Reverse all the transitions of the FA and interchange the positions of start state and final state. This is the FA equivalent to the original left linear grammar G. Example 3.2 : Construct an FA for following left linear > grammar. $5100 ‘Solution : (1) Reverse the RHS of the productions. S301S|0 (2) Modify the grammar as follows. Ss0A Asis S30 he equivalent FA is — CONTEXT FREE LANGUAGee G={N,T,P,S} € where N = fAo, Ab T = (a, b} and Agis the'start symbol. @ 8--8_9 Fig. 3.8 Solution : G =(N,T, P, S) Agis start symbol N= (Av Ay A.) T= (a,b) P= {Ay ay Ao bAL Arak: A. bAz|b Ar ahaa Az bAL o Stan z Fig. 39 Solution : G=(N,1.P.5) where N= (Aq Ay, Az, As) T= (a,b) Acis the start symbol and P= (A> bay Ar aly AL bA;| bAs |b G=(N,T,P,5) N=(S,A,C,B,D) T=,1)‘qicoRY OF COMPUTATION (COMP., BATU) 5) CONTEXT FREE LANGUAGES (CFL) p={S>0A/1B oon A= 1A] 0C|01 Soluti ee" ion: 8 18[1A]1D]1 ¢-0A0D}0) =o 6 3.4 : Construct the FA for the regular right linear Fig. 3.14 ig. 3. 2 (5) S 04/18 i. A>0C|1A|0 ‘= B—>18/1A|1 e 40] 0a 5. Solution : Bob Fig. 3.11, S+0A AsoAle ) $+ 0A| 18 As 1A\0C|0 8 18/1A|1 C5 0Aj0 Fig. 3.15 (© S>bB B—bC|aB|b Coa Solution : Start b b 2 ¥ Fig. 3.16 a Example 3.5 : Convert the following right linear grammar to | equivalent left linear grammar. (@) s>bB BbC| a8 |b Coa ‘Solution : () First we will convert the right linear grammar to a Transition graph. ‘ Fig. 3.17THEORY OF COMPUTATION (COMP., BATU) (i) Now interchange the positions of S and qy and reverse the direction of all transitions. Fig. 3.18 {i The corresponding left linear grammar is - S>Ca| Bb CB B—Ba|b 2) S08 B>10BJ< Solution : ()_ Right linear grammar to TG: 0 Start 0 © Fig. 3.19 (i) Interchange S and qj and reverse the direction ofall transitions. 10 © of s_@.2 Fig. 3.20 ii) The final corresponding left linear grammar is S38 B—B10|0 jaB Bs) Gi) Interchange the position of S and g , reverse all the transition arrows, Fig. 3.22 (i) The corresponding left linear grammars g by SB1]A0| CO A>A1|0/B1}CO B> 81/1 c>A0 SS eae Example 3.6 : Convert the following left linear gramma equivalent right linear grammar. (1) Sa] Bb BBa|b C>Bb Solution : (The TG corresponding to the left linear grammaris Start Fig. 3.23 (i) Interchange S and q; and reverse the direction of transition arrows, Fig. 3.24 Ai) The equivalent right linear grammars > > bB Bo aBibC]b CoapRY OF COMPUTATION (COM {@ TG of the above left linear grammar is - O % Fig. 325 fi) Interchange the positions of S and qf and reverse the arrows of all transitions. o 2 9 @ = 40 Fig. 3.26 So the equivalent right linear grammar is given by following rules. S—0A A+ 10AJe Bilt A1|B1|CO|0 interchange the position of S and qf reverse the direction of all transition a7 CONTEXT FREE LANGUAGES (CFL) i) The final right linear grammar is given by S—1B|0A A> 1A|0C}0 B > 1B/1A]1 C+ 0AJ0 [3.5 NORMALFORMS In a CFG, the RHS of a production can be any string of variables and terminals. When the productions in G satisfy particular restrictions, then G is said to be in a “normal form", Among several normal forms we are going to study the Chomsky normal form and the Greibach normal form. Chomsky Normal Form (CNF) In the Chomsky normal form we have restrictions on the length of RHS and the nature of symbols in the RHS of productions. Definition : A context free grammar G is in Chomsky normal form (CNF) if every production is of one of the two following types. ABC Ava 5 and S ~¢ isin Gife isin). When e is in L(G) we assume that S does not appear on the RHS of any producti Example 3.7 : Let G be a CFG with Productions S>ABle Ava Bob Then Gis in CNF. ‘Solution : To put a grammar G in CNF we have to follow the following steps - Step 1: Find an equivalent grammar G' which has no (a) € - productions (6) unit productions and (©) useless symbols Step 2 : Restrict the right hand side of all productions to igle terminal (A — a) or strings of two or more variables (A > BO) Step 3 : Break the RHS of length 3 or more into a cascade of productions, each with a body consisting of two variables.‘THEORY OF COMPUTATION (COMP., BATU) For example, S —> ABA Avadle B—>bBle (1) Removing the useless symbols : S, A B are generating and A, B are reachable symbols, So there are no useless symbols in G. (2) Removing € productions. G =(S-> ABA] AB|BA| AA] A|B Asaala BbB|b) (3) Removing unit productions : Unit productions in G are S > Aand S 8. G = {S > ABA] AB|BA|AA| aA |a| bB |b. Asaala B—>bB|b } (4) Restrict the RHS of all productions to a single terminal or 2 or more variables. The grammar in CNFis: SAR, [AB] BA|AA|RA|a|R:B |b RBA Roa Rb AsRAla BRB |b. 'Greibach Normal Form (GNF) Normal Form is useful in some proofs and +A context free grammar G is in Greibach Form if every production is of the form A > a a. Ge N*andac T,amay bee andS—e isinGite UG). When ¢ is in L(G) assume that $ does not appear the RHS of any production, 9 @ grammar to this form is complex even if we the task by starting with CNF. GNF has several ing consequences. Each use of a production s exactly one terminal into a sentential from a gth n has a derivation of exactly n steps. a) CONTEXT FREE LANGUAGes e Example 3.8 : 5 > ABA|AB|BA|AA|A|B AdAla B > bB|b. Solution: A aA|a B— bB | b are already in necessary form. S— aABA | aBA | aAB | aB | bBA| bA| aAA| aA aA lat, Example 3.9 : Given a grammar G, find L(G). (2) G = (5), (0, bP, S} P=(SaSb Se} Solution : f) Soe, cael €€ L(G) S>aSb —aaSbb aa bb sab (i) S+asb ab Sasb aaSbb 2a aSb bb sab +a" b"€ L(G) forn 20. @) G=({9, 0)(S +55.) Solution : (i) S -> SS is the only production in P which! ‘ot producing any terminal symbol. «. L(G) = 6. ) G = (S), (0, 1, P, P=(S50|1le S00 So isl) Solution : @ Se (i) Sao (i) So. (iv) S 0s0 ) Soso 01810 0110.y OF COMPUTATION (COMP., BATU) arefully Sis generating the stings that are 13 01> 00 os os os 011 or 010 1s ois 10s ous = 1010 S is generating a string of 0's and 1's with bheuedbuuevyoude G= {5}, {2,b, od, P, S) P=( Sasa S—bsb abSba 3 = “4 ~ 5 4 By ® x (3.9) CONTEXT FREE LANGUAGES (CFL) Example 3.10 : Give a grammar generating the strings of language 1. @) L= (a"ba n> 1) Solution : When n = 1 The 1” possible string is aba. P=( Saha 4 A-aha|b) G=((5,A), (0, 6}, P, S} (2) Lis a set of all palindromes over (0, 1} Solution : We know that palindrome is a word that reads same in forward and backward direction. P=(S+elo|1 S$ 0s0 sisi ) (8) L consists of stings over {0, 1)*-with atleast one ‘occurrence of 000. Solution : At least one occurrence of 000 can be given by 2 regular expression (0 +1)" 0000 + 1)* = P={S>A000A AOA IAle ’ G=(1SA),, 11°, 5). @ fab Ji20,j21) Solution : P=(Sas|A “A bAc| be ss } (5) L contains all strings with no consecutive b's but may be with consecutive a's. Solution: P=(S—aS|bT)a/ble Toaslale } ‘Example 3.11 : Find the CFL associated with given CFG. (2) G = ( (5) {a}, (S > aS}, Se}, S) Solution : Sr. Sas Sas > aaas aa + LUG) = (a)* pn~ EET Ur Cumrunqunure (ume wre ey 1 (2) S0A| 1B A 18/1 B0A|0 Solution : ¥ L s o1 0A 018 010 1B 10° 18 0A > 101 The CFG generates the strings with alternate sequence of 0's and 1's with minimum length of string = 1. (3) P= {S > aS| bT|a| bT— aS | a} Solution : PS ee bo Soa Sab Sas. —abT > abas > abaas, = abaab observe carefully a is allowed to occur after a and b But b is not allowed to occur immediately after b. So CFG generates strings in which no consecutive b’s are (5) S+as|bSl€ Solution : ase (i) S > aS >a (ii) S > aS => abS > ab (ws > bs 3b mS > bs > bas — ba ) S > bs > bbs > bbaS — bba L={e,a,b, ab, ba, L=@+b) (6) Sry x aX|bX|a yoyalybla Solution : Consider the production X—ak|bX|a It produces strings of a's and b’s ending with a. Consider y — ya | yb | a It produces the strings that are starting with a. Say Xends with a and y starts with a. Therefore S produce the strings with atleast one occurrence of Example 3.12 : Write the CFG for given CFL's (2) CFL contains the strings with equal number of and b's. Solution : CFL contains the strings with equal number a's and b's. ie. if is there, there must be one b and vi* versa. j SaB|bA Analasiban B-b|bS| aBBysoR’ OF COMPUTATION (COMP. BATU) {@) L contains the strings of any number of a's with z=) ution : (1) number of a's (2) number of a's = @) number of a's = 2 p=(Se lalas} {@) L contains the strings consisting of a's and b's with at least two a's. jon : The atleast 2 a's can be expressed in Re as (a+ byta (a+ byt ala + by refore the productions of the grammar G can be given S+AaAaAd A>aA|bAle (@) L=ab* S>aB BB <. (5) L=at bt SAB Asahle Bo bBle. (6) L = (baa + abb)* S+AS|BS|e A baa Babb (7) L contains the words over alphabet (a, b) Containing words that have different fist and last letters. + If the word starts with a, it must end with b and versa, SsaAb|bAa An ak|bAle. L contains the words with allowed but no consecutive b's. consecutive. a's S—aS|bx|a|b XaS|a a1) CONTEXT FREE LANGUAGES (CFL) Example 3.13: Convert the following grammar to GNF. SABC A~a A~b B>Bb Baa Cac Cocc C >ba where N=(S A,B,C) T= (0,6) Solution : We shall consider each rule one by one and check whether it is in GNF or not. If it is not in GNF we shall convert it to GNF form, (@) SABC We have to replace A on the RHS to the terminal symbol. We know that A> aand Aab S05 + ABCwill be now S—>aBC . and S+bBC (2) A>aisin GNF. @) A bis in GNF (@) 8 Bb Here we have to make the RHS as starting with terminal followed by the non-terminals. So, we have to convert B to start with terminal with trailing non-terminals. Lets introduce one non-terminal P as follows : PobP Pob andR a So BaRP : (5) Bea, We can write this rule as B > aR (© C>aCisinGNF (7) C>cCisin GNF - (@) C>ba.We can write this rule as C > b R= THEORY OF COMPUTATION (COMP., BATU) (2) CONTEXT FREE LANGUAGES (cr) So the given grammar is GNF is as follows : S>aBc S>aBC Asalb BaP Roa Boar Cac coec C5bR 3.5.3 Closure Properties of CFL Like regular languages, the context free languages are closed under union, concatenation and Kleene star. Unlike regular languages, CFL's are not closed under intersection and complement CFL's are closed under union if L(G) = L(G1) U (G2), and if (G1) and (G2) are. context free languages, then L(G) is also context free guage. *s are closed under concatenation Let Ly and L; be CFL's. Then LiL, is also context a context free language. is CFL then L:* is also context free language. CFLs closed under kleene’s closure, ‘non-deterministic pushdown automata of information about them. We know that lem is solvable, but the £* problem ‘over E are in the language) and the are unsolvable. It revealed that thi under the operations of union, Kleene star. || This is all we need. Part (a) of the theorem is obviously true Lemma (Pumping) : For every context free language , there is an integer n such that for any string z in L Whose length is at least n: (a) there exist u, v, w, x.y such that z = uvwxy, (0) wx#e, (© the length of vwx < 2n, and (A) for all, uviwxiy € L. Proof : Let G = (NJ,P.S) be a Chomsky normal form grammar for L with k non-terminal symbols. Let z € L(G) be at least 2 k characters long. Let's also set n = 2k and claim that this is the n we are looking for. Consider the derivation tree for this string z. Since G isin Chomsky Normal form the entire tree except for the edges leading to the leaves is binary. We know that the shortest binary tree with 2k leaves has height k. Thus the derivation tree for the string z must contain paths of more than k non-terminal symbols since z is longer than 2k. Let us now select the longest path in the derivation tree. ‘As we stated above, there are more than k non-terminal symbols on this longest path. Thus a non-terminal symbol ‘must be ‘repeated along it. (There are only k of these ~ remember ?) Let us start at the leaf on this path and go up the tree. We now find the first non-terminal symbol which appears twice and call it A. We also mark the two occurrences of this symbol A which are closest to the bottom of the tree. This is illustrated in Fig. 3.29. s 77 | Fig. 3.29 : Derivation tree for z < L(G) In Fig. 329 we also depicted the assignment of u, v, w, X and y such that : S generates uwwny = z, A generates vwx, and A generates w. i since z = uvway. Since the non-terminals on the path from | * A to A do generate terminal symbols, both u and v cannot be empty. (In fact, if A > BA, then v still contains some terminals since B will generate a terminal string.) Thus part. (b) is correct also. Part (c) depends upon the fact that We” selected the longest path and set A to be the non-terminal a & 'HEORY OF COMPUTATION (COMP., BATU) yhich repeated closest to the bottom of the-derivation ree. Thus the path from the top A in Fig, 3.29 to the leaves annot contain more than k#+1 non-terminals (including the wo A's). A binary derivation tree of this height can produce st most 2k+1 = 2n terminals. ail that remains is to verify part (d) of the theorem. Here are some more pictures. In Fig, 3.29 we collapse the path from A to A. 8 : 7 y Fig. 3.30 : Derivation Tree for uwy is generates uwy = uvOwx0y. Since it is a valid derivation ‘our grammar G, uwy must be a member of the language next illustration (Fig. 3.30) reveals what takes place ‘we repeat the path from A to A one more time, § Fig. 3.31 : Derivation Tree for uvvwoxy string uvwwory = uv2wr2y is generated this time. ‘also be a member of the language L. In a like manner strings of the form uviwxiy can be generated by the mar G for L ‘5 the pumping lemma for regular 5 strate that there are some non-regul the context free language pumping lemma to show Rot all languages are context free. 5 11n0n is not ets was used to lar sets, we shall 3.1 : The set of strings of the form On. free. +: We use almost the same argument that we invoked that strings of the form anbn were not regular, We ame that strings of the form * are context free. Then we apply the pumping and state that there is some integer m such that for stting at least m in length of the form OntnOn satisfies conditions of the pumping lemma. We shall 9° 2 bit (3.13) CONTEXT FREE LANGUAGES (CFL) overboard and let this: string be Om1mOm, We know the pumping lemma assures us that : (@) There exist u, v, w, x and y such that uwwxy = Omim0m, (b) (©) for all i, uvwxy is of the form 0°10". vx#e, and We now observe that either v and x each contain only one kind of symbol (0 or 1), or at least one of them contains some zeros and some ones. In either case the string uv’wzy cannot be of the form 0°10", because either the runs of zeros and ones will not be of the same length, or there will be more than three sequences. Since the set of strings of the form 0°1°0" is a context sensitive language we may now state a corollary to our last theorem. Corollary : The context free languages are a strict subclass of the context sensitive languages. Other results which follow quickly from the pumping lemma and the fact that 0°1"0" is not context free are two non-closure properties. The second (complement) is just an application of DeMorgan’s Laws. Theorem 3.2 : The family of context free languages is not closed under intersection. Proof : Here are two context free grammars. S>AB SBA SA SA A>0Al A> 1A0 A501 A>10 B08 BOB B30 Bo It is evident that the languages generated by these ‘grammars are the sets of strings of the form 0°1"0* and 0*1°0" for values of n > 1. The intersection of these languages is merely our old friend 0°2"0". So, the context free languages cannot be closed under intersection. Theorem 3.3 : The family of context free languages is not closed under complement. Proof : To close out our examination of context free language properties we tum to decision problems. Our study of pushdown machines lead to the unsolvability of equivalence, cofiniteness, and whether the language contained all strings. Now we yet again bring out the pumping lemma to show that emptiness is solvable,THEORY OF COMPUTATION (COMP., BATU) (3.14) CONTEXT FREE LANGUAGES (cs, Theorem 3.4 : The emptiness problem is solvable for context free languages. Proof : Given a Chomsky Normal Form grammar, we claim that it will generate a string of length less than 2" (where as in the pumping lemma, k is the number of non-terminals) if, it generates any strings at all. The justification for this claim is that if the shortest string in the language is longer than 2* symbols, we can apply the pumping lemma and shorten. it. Thus a check of all strings up to 2 in length forms an inefficient algorithm for emptiness. In order to show that finiteness is also solvable for the family of context free languages we could merely trot out the pumping lemma and look at strings longer than 2* in length. (In fact, prove this as an interesting exercise |!) Instead, we shall carry out some transformations on context free grammars which make them nice enough to almost solve finiteness for us. Definition : A useless non-terminal symbol is one which generates no strings of terminals. Theorem 3.5 : Every context free language can be generated ‘by a grammar which contains no useless non-terminals. Proof : First we detect the useless symbols and then discard them. To find out if a symbol is useless, just make it the starting symbol and check for emptiness. Easy as that. Now we toss out all productions containing useless non- inals and claim that the grammar generates the same language. (Note that if a non-terminal never generates a terminal string, then productions containing it will not lead ‘to terminal strings either.) Definition : An unreachable non-terminal symbol is one ich cannot be generated from the starting symbol. Theorem 3.6 : Every context free language can be generated ~ by a grammar which contains no unreachable non-terminal. __ Proof : We need one other bit of business before unveiling |Our finiteness algorithm. A transition diagram for context free grammars. This is just a graph with non-terminals as vertices and directed edges going from one non-terminal to another if they are on different sides of the same production. (The direction is from left to right) In other words, an edge in the graph means that one non-terminal generates another. Fig. 3.32 illustrates this for a grammar _ which generates our constant companion : strings of the eye 2 gee soc Coa sob (e) %) Fig. 3.32 : Grammar and Transition Diagram Theorem 3.7 : The finiteness problem is solvable for context free languages. Proof : We begin by making some observations. If 3 language is infinite then it has strings of arbitrary length Long strings have high derivation trees which have repeating non-terminals on paths through the tree. And, repeating non-terminals signify infinite languages. So, we must detect repeating non-terminals. First, we produce 2 grammar for the language which contains no useless or unreachable non-terminals. Next, we draw the transition diagram for the grammar. At this point we maintain that if there is a cycle in the transition diagram then a non- terminal can be repeated in a derivation. And, if there is 2 derivation with a repeating non-terminal, then there must be a cycle in the diagram because the non-terminal eventually generates itself. Thus, detecting cycles in the transition diagram reveals whether or not a grammar generates an infinite language. Type 0 oF Unrestricted (All Possible Grammars) Free grammars have absolutely no restrictions on their grammar rules, (except, of course, that there must be at least one non-terminal on the left-hand-side) of (a. 8). The type of automata which can recognise such a language is basically @ NFA/DFA with an infinitely-long list at its disposal to use as a store; this is called a Turing machine. Languages generated are recognized by Turing machines (automata that read from and write on an endless tape. which will be in studying chapter 5). Recognizing a string outputting “yes” if the string belongs to the language. Type 1 or Context-Sensitive B never shorter than o, jal < |B] (except for $ — €): Languages generated are recognized by linearly-bounded ‘automata (LBA) (a subclass of Turing machines) Context-Sensitive grammars may have more than one symbol on the left-hand-side of their production rules (provided that at least one of them is a non-terminal) However, the production rules must now obey the following : = a’b".queoRY OF COMPUTATION (COMP, BATU) aes eee ee ot pe number of symbols on the left:hand-side must not exceed the number of symbols on the right-hand-side, sz We do not allow rules of the form A> © unless A is the start symbol and does not occur on the right-hand-side of anyrule. ‘Soce we allow more than one symbol on the left-hand- de, we refer to those symbols other than the one we are replacing as the context of the replacement. The automaton which recognises a context-sensitive Ianguage is called a linear-bounded automaton : this is basically @ NFA/DFA which can store symbols in alist. ‘Conditions CS1 and CS2 above mean that the sentential form in any derivation must always increase in length every ‘tine a production rule is applied. This basically means that ‘the size of a sentential form is bounded by the length of the sentence (ie. word) we are deriving. Since the sentential form cannot thus grow infinitely large deriving Example 3.14 : Write CFG for the following languages. @ L={070'G>i+K ; _ @ Matching Parenthesis (ii) All strings with atleast 2 a's alphabet = (a, b) 2@) L=(OH0'4>i+K): SA’ A OB)Ble Bo 116 A BOpBle (i) Matching Parenthesis : ‘A.grammar for matching parenthesis is as follows : G=(,1,P,5) Ve(s) e . T={(,)) Passe |(5)|55 (3.15) CONTEXT FREE LANGUAGES (CFL) We can check this be rewriting an input string: MOOCO))) telat) {60S inside S is epsilon (C0) 0) S$ )) S48) (CO) SS. )) S-4(S)where the inside S is epsilon ) ) ) $-+(S) where the OC te eee Py Sat Se (( SS )) S-+(S)where the inside S is epsilon Ek S yy Ss (as ) S46) s so) ‘Thus the string ((() () (()))) is accepted by G because the rewriting produced exactly 5, the start variable. All strings with atleast 2 a's alphabet = (a, b} : S > Aahan AaaA|bAle Example 3.15 : Find GNF of the grammar given below : S > ABAb/ab BO ABA/a A a/b Solution : The given grammar has productions : S > ABAb Sab Bo aBA Boa Ava Asb Let us consider S > ABAD which can be fi SaBAb S bBAb (1) Let X > b so So (1) will be now S aBAX & _S—>bBAX Consider S ~» ab which can be written as Sax Now consider B > ABA ~ B>aBA S=sTHEORY OF COMPUTATION (COMP., BATU) B16) SOE ea B—bBA (a) A>a, Bob and (b) S—> aAbB Boa Let Asa Xoa yob Azb So X>b { S>XAyB is the grammar in GNF. AOXA Example 3.16 : Give CFG for the following Boys) @ L=@biXAYB oe oe 2 Ibiij2siiz1) Le SC AsbaA|* GAC, where (i) L= @besi+j=qij20 Gays SasclA So the grammar in CNF is ~ AabAc|* ESQ, A>XA yob Example 3.17 : Convert following RG to DFA G3 AC, BoyB Ava S—0A/1B GoyB Xa Bob } Ses OCA Example 3.19 : Give the GNF for following CFG : Bo 1B/1A/1 Cc 0/0A eee A BS/b Bo SA/a Example 3.18 : Find CNF equivalent to S— aAbB Avahla |B bB/b Solution : The given grammar is* ‘S— aAbB Anan Ava bbe Bob Solution : The grammar is already in CNF. Now rename S, A, Bas Ay, Az and A; respectively. AL > AAS Ar AyAlb As AAa Now, consider, A> AiR. using Lemma rule, AMAA: Now, applying the lemma once again, we get A AAA: | BAAD Now, A> A,ALAVAy is written as, As abAAIAAALA, Here,By = a, By = bA,A: and a ‘So, we get * Ayal AA: WASAgsr#p0RY OF COMPUTATION (COMP. BATU) 3.17) CONTEXT FREE LANGUAGES (CFL) Bee (2) Consider = Zp AMA | ADASAZs as pa 71 BA (ez | bees S— aAb BB will become Re S + aAb BB will be become vA: |b aoe S$ aA x BB which is in GNF. Be ee EN See EN NE (b) S+BB 8 will become S > a88 pee (3) Consider AAA A> DASJRAAIDAAAASIAZSAAIDALALZ,A:A\Z, juctions are modified as, Zs AAAIAAALAS ‘Applying lemma rule, we get - Zy > DASA:AIbA,ALALZ3 Zs > aM AsAsADALASASAxZs Zy > DAAAAAAIDAAAASASALZs Ty aL AAA ALAA A AZ: Ty > DASALZA:ASAsAa|DAZADZsArAAAaZ3 The grammar is now in GNF. 3.20: Reduce the grammar to GNF. SAB ABB A+ BSB A>aAb As>b Asb Boa Boa : Consider S > AB. Replace A by possible ctions. . ‘Now, SoBse B A> BBB , BobB Considers BS BB Replace B by possible productions. S—ahb sBB Sa SBB re: 4 X45 then S— aA x SBB / aSBB is in GNF. Sb Bis already in GNF. (4) Con: ler A+ BSB/BB (a) Consider A +B SB first. A>aAbsB = A aA x SB (b) Consider A > BB A>aAbB AsaAxB A>asB Aa SBis in GNF A~aBisin GNF (8) Now consider BoaAb Ba AX is in GNF. So the grammar in GNF is given by — { S > aAxSBB/as6B S — aAx BB/aBB — bB > aA x SB/asB > aAxB/aB > aAx +b mex o> > >a A 3b. RS ee eee Example 3.21 : Convert the following grammar to CNF : S$ — aba, S > aab, B > AC Solution : Step 1 : Symbol B is non-reachable. The symbol can be deleted. The grammar after simplification is : S$ Aba | aabCONTEXT FREE LANGUAGES, THEORY OF COMPUTATION (COMP., BATU) 3.18) re —Stop-2+ Replace X vane PFD U=FaD- —— SPQ SAP re Sey Po yx SE S+ AQ Soe Q> Xx $30 The final P for G to be in CNF given by S90, P= {Sap sal Poyx Pp YP|0 S+aQ Q> YQ|1 Qo xx x30 X=a Yb} You Example 3.22: Convert the grammar given below to its | Example 3.23 : Construct a grammar in GNF which é equivalent CNF equivalent to grammar Ss POP S> Asa P+ OPle Aa SS|b Q>1Qle Solution : The grammar is already in CNF. Now rename Solution : (i) Removal of useless symbols. S. P, Q are all-generating non-terminals. So there is no useless symbol in P. (i) Removal of ¢ productions. Removal of P< andQ > Pr = {S— PQP|PQ|QP|P|Q P—o0P|O Q>1Q1H (ii) Removal of unit productions. There are two unit productions. SP andS+Q Removal of unit production, P’ (S> PQP|PQ|.QP| OP | 0/1911) Pp P oP|o Q> 1Q)1 It can be converted into CNF by X30, Y31 5 PQP will be A> PQ SAP variables S and A are A; and A, respectively. AL A.A? Acta A> MAL Mob Applying Lemma rule to A, Al A=1A, > Ar > AaAaAy, Ay aA: The resulting production is A> AA la A2 > ArAoA; | aA, | b Removing left recursion Az aA.B,| bB, Bo AAB2 | AAL Reselling set of production is A> AAQ|a Ar > @A.B, | aB;| aA, |b Ba > AAiBa | Ary ‘Az production are in GNF, ‘A. and Br productions can be converted to GNF wit” AIF the help of Az production{qygoRY OF COMPUTATION (COMP. BATU) Se, 9) Aa aA,B2 | bB2| aA,| b AL > AA? Substitute aA,B; | bB2 | aA; |b for find A; q ‘AL > @AB2A2 | bB2A2 | aA\A, | bA, A, > a in GNF low for B2 producting By > AxAB, “Substituting for A, By > aA:B2AB | bB:A,By | aAA,B, | bA:B, Bp AA, By aA:ByA; | bB2A; | aAiA; | bAy The final set of production is A. —> aA.B,| bB,| aA: |b A, > aA:B2A2 | bB2A2 | aArA2| bA| a Bz + aA;B2A,B,|bB,A] Bz | aA:A,B, | bA:B, | @A:B2Ay | BBA; | aAsAx | DAL rt the given right linear grammar into its lent left linear grammar. CONTEXT FREE LANGUAGES (CFL) 5. Give context free~ grammars. for- the~ following languages (a) L={a"b™[n>=0) Convert the given right linear grammar to its equivalent left linear form S—aA|bB Abe Bac Cal |bC}a| Construct a DFA for the following left linear grammar SBI] A0| co BoB1|1 A—A1(B1|CO|0 cao State and explain closure properties of Context Free Languages Convert the following CFG to CNF SABA Aaable BbBle Obtain a DFA accepting the regular language defined by the following right linear grammar 10. S>Al1B A+C/IAI0 B18 /1A|1 C-40]0A Convert the following CFG to CNF SABA A>BS|b Bo Sala i. Construct a grammar G to represent a language L which isa set of all palindromes over (a, b} 12. Find a-grammar in Greiabch Normal form equivalent to the grammar. S$ 1A| 08 A> 1AA| 050 088 |/1S|1 23.THEORY OF COMPUTATION (COMP... BATU) eee) CONTEXT FREE LANGUAGE, y simplify and convert the following CFG to Cha 14. For the right linear grammar given below, obtain an | 23: equivalent left linear grammar: Normal Form S$ 10A]01 5 —AACD A> 00A}1 A-abble 15. Describe the language generated by following Coacla grammar. D-—aDa| bDb/£ Beeee|aN le 2A. Convert the following grammar to GNF = A-yaA|bB| b S$ > ABA|AB|BA|AAIAIB Bobs AvaAla 16. Convert the following CFG to Chomsky Normal Form, B—bB|b S— Aba 25. Convert the following grammar to CNF Saab (a) S>AACD BSc () As aable 17. Find a grammar in Greiabch Normal form equivalent (© C>aCcla to the E foe (@) A-aDa| bb |e S—>1A|0B ae 26. Describe the language generated by each of thes A 1AA| 050 grammar and justify your answer with the exam BBB} 1S|1 string derive from the grammar of the production 18. Convert the following grammar to Greibach normal guenelew= from the grammar: (@) S—aSa|bSb | aAb| baa G = (Ay, Aa, Aaa, bh, P, Ay) A-ada|bAb|a|b|e ‘Where P cor f the following : y z S>bTlaTle A Aa AS Tas Ar Asal ee Ai 3 NASI (b) Saa|bs ; 19. Convert the following grammar to Greibach normal A aS|bB form the grammar BaC|bAla S>§5, $051] 01 = ! - 27. Prove that L = {a'b'c'|1> 1} is not a CFL. 20._ Justify whether following grammars are in CNF or no = 1 SAS|a 28, Prove that L = {a’ bic! i> isnot acrL. Aa sAlb 29. In each case, find a CFG generating the give 2. SAS|AAS pe es Boanaae ASSA|aa (@) The set of all length strings in (a, b) « with midd! 21. Write a note on applications of CFG. symbol a, 22. Convert the following CFG to Chomsky Normal Form, (b) The set of even length strings in (a, b} * with th S—aB|bA two middle symbols equal. A—alaS| bAA Bob eae ee : : i Se aul ist: middle and last symbols are all same.irony OF COMPUTATION (COMP, BAT! _@21 |. Show that L = {a” b"c" | n 2 1) isnot context free but context sensitive. f, (A) Construct a grammar in GNF equivalent to the ‘grammar 5 AA|aand A SS|b {8) Write a short note on types of grammar. (© Ifthe grammar given by the productions S+aSalbSblaa|bb| 4, show that () LQ) has no strings of odd length i) Any string in L(G) is of length 2n, n > Oand “fi) The number of strings of length 2n is 2” ‘If the grammar given by the productions § —> asa | "bs | aa | bb | * Show that, L(G) has no strings of odd length Any string in L(G) is of length 2n, n > 0 and ii) The number of strings of length 2n is 2” st the following grammar into its equivalent + AB, A> BS|b,B > SAla that following are not context-free languages : The set of all strings over {a, b, c} in which the number of occurances of a, b, cis the same, fa" b™ "| msns2m) ibe the terms, ‘left-linear’ end ‘right-Linear’ mar. the following left linear grammar to its valent right linear grammar. B1]A0|CO, A> CO|A1/B1/0 B1)1,C a0 39, 40. 41, 42. 43, 45, 46. 47. 48. 49. 5L 52. 53. CONTEXT FREE LANGUAGES (CFL) Write short note on CNF. Write CFG for matching parentheses, For the following CFG, find regular expression that define the same language S—aB| bA A-abla BobA|b Define type 0 and type 1 grammar. Describe GNF with an example. Convert the following grammar into CNF. S—bA|aB A bAA|aS|a B > aBB | bS|b Convert the following CFG into CNF: S— aSb | bSb| a| b | aa| bb Explain with an example the Greibach Normal Form. 1s the language L= (a'|b"|n # m) context free ? If yes, write CFG defining the above language. If no, prove it, Write a Grammar to generate a language L=(a°b’c" Where n = 1, 2, .) Write a short note on Derivation graph. Write a CFG (context free grammar) which defines a language L over 5 = (a, b) such that L contains the words in which the letter b is never tripled. Convert the following grammar to CNF SABA, A> aAle, B>bBle Is the language L = {a°b" | n # m} context free ? If yes, write CFG defining the above language. If no, prove it Write short note on Griebach Normal form. Convert the following right linear grammar to equivalent left linear grammar S$ aA|bBlaS|a A>bAle BoaBle Write short note on Applications of CFG,THEORY OF COMPUTATION (COMP. BATU) (3.22) 56. 57. 58. 59, Distinguish between type 0 and type 1 grammar. Write short note on Griebach Normal Form (with example). Write context free grammar (CFG) which defines the | 62. language L, given by : (a+b)*bbb(a+b)*, Convert the following grammar to CNF : 63 SABA, A aA|e,B > bB le Find the CFL associated with the CFG given below : S>aB|bA A alaS|bAA, B->b|bs| aBB CONTEXT FREE LANGUAGES 5, 61. Give Regular expression for language generate 4, following grammar : SA[B,A—OAle,B>0B/Ble Show that the context free languages are clos Under union, concatenation and kleen star. Consider the following two languages L.= (abc | n, m >= 0} Ly = fa"b"C" | n, m >= 0) Is Ly A Ly a context free language ? Justify. ROW