2160704_TOC_GTU_Study_Material_Presentations_Unit-3_22022020072212AM.pptx

2160704 Theory of Computation Unit-3 Context Free Grammar Prof. Dixita B. Kagathara Dixita.kagathara@darshan. ac.in Darshan Darshan Institute Institute of...

2160704 Theory of Computation Unit-3 Context Free Grammar Prof. Dixita B. Kagathara Dixita.kagathara@darshan. ac.in Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Theory of of Computation Computation (2160704) (2160704) 1 1  Topics to be covered Chomsky hierarchy Context free grammar Recursive definition FA to regular grammar Derivation Ambiguity & unambiguous grammar Simplified forms & normal forms CFG to CNF Union, Concatenation & Kleene’s of CFG Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 2 2  Chomsky Hierarchy Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free Computation Context (2160704) Free Grammar (2160704) Grammar 3 3  Chomsky hierarchy (Classification of grammar) Grammar Unrestricted Restricted grammar grammar (type 0) Contex Contex Regula t t free r sensiti gramm gramm ve ar(type ar(type gramm 2) 3) ar (type 1) Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 4 4  Type 0 grammar (Phrase Structure Grammar) Their productions are of the form: where both and can be strings of terminal and nonterminal symbols. Example: S → ACaB Bc → acB CB → DB aD → Db Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 5 5  Type 1 grammar (Context Sensitive Grammar) Their productions are of the form: where A is non terminal and , , are strings of terminals and non terminals. The strings and may be empty, but must be non- empty. Here, a string can be replaced by (or vice versa) only when it is enclosed by the strings and in a sentential form. Example: AB → AbBc A → bcA B→b Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 6 6  Type 2 grammar (Context Free Grammar) Their productions are of the form: Where is non terminal and is string of terminals and non terminals. Example: S → Xa X→a X → aX X → abc Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 7 7  Type 3 grammar (Linear or Regular grammar) Their productions are of the form: or Where are non terminals and is terminal. Example: X → a | aY Y→b Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 8 8  Hierarchy of grammar Type 3 (Regular) Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) Grammar (2160704) 9 9  Context free grammar Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 10 Grammar 10  Context Free Grammar A context free grammar (CFG) is a 4-tuple where, is finite set of non terminals, is disjoint finite set of terminals, is an element of and it’s a start symbol, is a finite set of productions of the form where and. Application of CFG: 1. CFG are extensively used to specify the syntax of programming language. 2. CFG is used to develop a parser. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 11 Grammar 11  Context Free Language Let be a CFG. The language generated by is A language is a context free Language (CFL) if there is a CFG so that. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 12 Grammar 12  CFG Examples Write CFG for either a or b Sa | b Write CFG for a+ S aS | a Write CFG for a* S aS | ^ Write CFG for (ab)* SabS | ^ Write CFG for any string of a and b S aS | bS | a | b Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 13 Grammar 13  CFG Examples Write CFG for ab* SaX X˄| bX Write CFG for a*b* SXY XaX|˄ YbY|˄ Write CFG for (a+b)* SaS | bS | ^ Write CFG for a(a+b)* SaX XaX | bX | ^ Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 14 Grammar 14  CFG Examples Write CFG for a* | b* SA | B A˄| aA B^ |bB Write CFG for (011+1)*(01)* SAB A011A | 1A | ^ B01B | ^ Write CFG for balanced parenthesis S [] | {} | [s] | {s} | ^ Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 15 Grammar 15  CFG Examples Write CFG which contains at least three times 1. SA1A1A1A A0A | 1A | ^ Write CFG that must start and end with same symbol. S0A0 | 1A1 A0A | 1A | ^ The language of even & odd length palindrome string over {a,b} SaSa|bSb|a|b|˄ No. of a and no. of b are same SaSb|bSa|˄ Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 16 Grammar 16  CFG Examples Write CFG for regular expression (a+b)*a(a+b)*a(a+b)* SXaXaX XaX|bX|˄ Write CFG for number of 0’s and 1’s are same (n0(x)=n1(x)) S0S1 | 1S0 | ^ Write CFG for L={aibjck | i=j or j=k} For i=j for j=k SAB SCD AaAb | ab CaC | a BcB | c DbDc | bc Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 17 Grammar 17  CFG Examples Write CFG for L={ aibjck | j>i+k} SABC AaAb |˄ BbB | b CbCc |˄ Write CFG for L={ 0i1j0k | j>i+k} SABC A0A1 |˄ B1B | 1 C1C0 |˄ Write CFG for the language of Algebraic expressions Darshan | a Institute Institute of of Engineering Engineering & Unit ––SS+S Theory Unit Theory 33of of | S*S :: Context Free |Grammar Free Computation Context Computation S-S | S/S 18 (2160704) Grammar (2160704) | (S) 18 Darshan &  CFG Examples FG for syntax of programming language … | | | … if ( ) for ( ; ; ) Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 19 Grammar 19  Recursive Definitions Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 20 Grammar 20  Recursive Definitions CFG: 1.Recursive Definition of S aS | bS | ^ {a,b}* ˄∈L. For any S∈L, aS∈L. For any S∈L, bS∈L. No other strings are in L. 2.Recursive Definition of Palindrome CFG: S aSa | bSb | a | b | ˄, a, b ∈ L For any S ∈ L , aSa ∈ L and bSb ∈ L No other string are in L 3.Recursive Definition of the language CFG: b {a S |aSb | ˄ n n n≥0} ˄∈ L For every S ∈ L, aSb ∈L Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit ––No Theory Theory 3 :: other 3of of strings Context Free Computation Context Computation are in L 21 Free Grammar (2160704) Grammar (2160704) 21  FA to Regular Grammar Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 22 Grammar 22  FA to Regular Grammar 1 0 𝐴→ 0 𝐴 0 𝐴→ 1𝐵 𝐵→ 0𝐶 𝐴 1 𝐵 𝐶 𝐵→ 1 𝐵 1 0 𝐶 →0 𝐴 𝐶 →1 𝐵 𝐵→ 0 At last, all the incoming transitions to the accepting states are designated by the production Source State → input symbol Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 23 Grammar 23  Exercise: FA to Regular Grammar b a B a b b A C b b a a a E D Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 24 Grammar 24  Derivation Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 25 Grammar 25  Derivation Derivation is used to find whether the string belongs to a given grammar or not. There are two types of derivation: 1. Leftmost derivation 2. Rightmost derivation Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 26 Grammar 26  Leftmost derivation A derivation of a string in a grammar is a left most derivation if at every step the left most non terminal is replaced. Grammar: SS+S | S-S | S*S | S/S | a Output string: a*a-a S S S - S S-S Parse tree represents the S*S-S structure of S * S a derivation a*S-S a a a*a-S Leftmost Parse tree a*a-a Derivation Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 27 Grammar 27  Rightmost derivation A derivation of a string in a grammar is a right most derivation if at every step the right most non terminal is replaced. It is all called canonical derivation. Grammar: SS+S | S-S | S*S | S/S | a SOutput string: a*a-a S S * S S*S S*S-S a S - S S*S-a a a S*a-a Rightmost Parse Tree a*a-a Derivation Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 28 Grammar 28  Example: Derivation SA1B A0A | 𝜖 B0B | 1B | 𝜖 Perform leftmost & Rightmost derivation. (String: 00101) Leftmost Derivation Rightmost Derivation S S A1B A1B A10B 0A1B A101B 00A1B A101 001B 0A101 0010B 00A101 00101B 00101 00101 Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 29 Grammar 29  Exercise: Derivation 1. Perform leftmost derivation and draw parse tree. SA1B A0A | 𝜖 B0B | 1B | 𝜖 Output string: 1001. 2. Perform rightmost derivation and draw parse tree. EE+E | E*E | id | (E) | -E Output string : id + id * id. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 30 Grammar 30  Ambiguous grammar Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 31 Grammar 31  Ambiguous grammar Ambiguous grammar is one that produces more than one leftmost or more then one rightmost derivation for the same sentence. Grammar: SS+S | S*S | (S) | a Output string: a+a*a S S S S S*S S+S S * S S + S S+S*S a+S S a+S*S a+S*S + S a a S * S a+a*S a+a*S a a+a*a a+a*a a a a Here, Two leftmost derivation for string a+a*a is possible hence, above grammar is ambiguous. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 32 Grammar 32  Exercise: Ambiguous grammar Check whether following grammars are ambiguous or not: 1. S aS | Sa | 𝜖 (string: aaaa) 2. S aSbS | bSaS | 𝜖 (string: abab) 3. SSS+ | SS* | a (string: aa+a*) Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 33 Grammar 33  Unambiguous grammar Grammar: S S+S | S*S | (S) | a Output string: Equivalent unambiguous grammar is a+a*a S S S + T | T Equivalent unambiguous  S+T T T * F | F grammar F (S) | a  T+T Try for second Not possible???? leftmost  F+T derivation  a+T  a+T*F Here, two left most derivation is not  a+F*F possible for string a+a*a hence, grammar is unambiguous.  a+a*F Darshan Darshan Institute Institute of of Engineering Unit Unit –– 3 Theory Theory :: Context 3of of Free Free Grammar Computation Context Computation (2160704) (2160704) 34 Grammar 34 a+a*a &&  Engineering  Simplified forms & Normal forms Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 35 Grammar 35  Nullable Variable A Nullable variable in a CFG, is defined as follows: 1. Any variable A for which P contains is nullable. 2. If P contains the production are nullable variable, then A is nullable. 3. No other variables in V are nullable. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 36 Grammar 36  Eliminate ˄ production Sa X | SaX | Yb | SaX|Yb|a Yb a^ XS X ˄ | S X^ | S YbY|b YbY|b YbY|b Replacing X by ^ in Nullable all productions Removing ^ variable={X} containing X on productions RHS and rewriting the production again Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 37 Grammar 37  Exercise: Eliminate ^ production SAC SXaX|bX|Y AaAb|˄ XXaX|XbX|˄ CaC|a Yab After elimination of ^ After elimination of ^ production: production: S XaX | bX | Y | aX | Xa | a | b SAC | C X XaX |XbX | aX | Xa | a | Xb | bX AaAb| ab |b CaC|a Yab Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 38 Grammar 38  A-derivable A variable is called A-derivable , 1. If is a production, B is A-derivable. 2. If C is A-derivable, is a production, and , then B is A-derivable. 3. No other variables are A-derivable. SA SA SB AB S- S- derivable={A, derivable={A, B} B} Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 39 Grammar 39  Unit Production & Elimination of Unit productions A production of the form AB is termed as unit production. Where A & B are nonterminals. Algorithm Given a CFG with no ^ productions, construct a CFG having no unit production as follows. 1. Initialize P1 to be P. 2. For each A ∈ V ,finding the set of A derivable variable. 3. For every pair (A, B) such that B is A- derivable and every non unit production Bα, add the production Aα to P1 if it is not already present in P1. Darshan Institute Unit ––4. Theory Unit Theory 3 ::Delete 3of ofContext all unit Free Computation Context Free Computation Grammar (2160704) Grammar (2160704) 40 40 Darshan productions from P1. of Institute of Engineering Engineering & &  Elimination of unit production SABA|BA|AA|AB|A| Unit B Productions A aA|a are SA and B bB|b SB SABA|BA|AA| |aA|a|bB|b Removing unit AaA|aAB BbB|b productions Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 41 Grammar 41  CFG to CNF Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 42 Grammar 42  Chomsky Normal Form (CNF) A context free grammar is in Chomsky normal form (CNF) if every production is one of these two forms: Where and are nonterminal and is terminal. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 43 Grammar 43  Converting CFG to CNF Steps to convert CFG to CNF 1. Eliminate ˄-Productions. 2. Eliminate Unit Productions. 3. Restricting the right side of productions to single terminal or string of two or more nonterminals. 4. Final step of CNF. (shorten the string of NT to length 2) Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 44 Grammar 44  Example: CFG to CNF Step 3: Replace all mixed string SAAC SAAC|AC|aC with solid NT PC|a AaAb|˄ A PAQ|PQ aAb|ab CaC|a C PC|a aC|a Pa Step 1: Elimination of ^ Qb production Eliminate A^ SAAC| AC |C Step-4: Shorten the string of NT to AaAb|ab length 2 CaC|a SAX1 X1AC SAC|PC|a Step-2: Eliminate Unit Unitis SC Production APY1 Y1AQ Production SAAC|AC|C aC|a APQ AaAb|ab CPC|a Chomsky Normal CaC|a Form Pa Darshan Institute of Engineering & Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 45 Grammar 45  Example: CFG to CNF SaAbB AAb|b BBa|a Step 1 and 2 are not required as there is no ^ and unit productions Step-4 : final step of CNF Step-3: Replace all mixed string with solid SPT1 NT SPAQB T1AT2 AAQ|b T2QB BBP|a AAQ|b BBP|a Pa Pa Qb Qb Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 46 Grammar 46  Example: CFG to CNF SAA AB|BB BabB|b|bb Step 1 is not required as there is no ^ productions Step-4 : Shorten the string of NT to Step-2: Eliminate Unit Production: length 2 SAA SAA A abB|b|bb|BB A PT1|b|QQ|BB T1QB BabB|b|bb B PV1|b|QQ V1QB Pa Step-3:Replace all mixed string with solid QbNT: SAA A PQB|b|QQ|BB B PQB|b|QQ Pa Qb Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 47 Grammar 47  Example: CFG to CNF SASB|^ AaAS|a BSbS|A|bb Step-3:Replace all mixed string with Step-1: Eliminate ˄-Production: solid NT: SASB|AB SASB|AB APAS|a|PA AaAS|a|aA BSQS|PAS|a|PA|QQ|QS|SQ|b BSbS|A|bb|bS|Sb|b Pa Step-2: Eliminate Unit Production: Qb Step-4 : Shorten the string of NT to SASB|AB length 2 AaAS|a|aA SAB|AT1 T1SB BSbS|aAS|a|aA|bb|bS|Sb|b Aa|PA|PU1 U1AS B SV1|PV2|a|PA|QQ|QS|SQ|b V1QS V2AS Pa Qb Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 48 Grammar 48  Backus-Naur Form (BNF) BNF is one of the notation Example: techniques for context free = + | grammar. It is often used to describe = * | syntax of the language used in computing. = ^ Variables written between | are non terminals. = | Vertical bar ‘|’ indicating a = alternate choice. =[+/-] […], which is used to =a | b | c |……| z enclosed an optional =0 | 1 |………….| 9 specification. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 49 Grammar 49  Union, Concatenation & Kleene’s of CFG Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 50 Grammar 50  Union, Concatenation & Kleene’s of CFG Theorem:- If L1 and L2 are context - free languages, then the languages L1 U L2, L1L2 , and L1* are also CFLs. The proof is constructive: Starting with CFGs G1 = (V1, Ʃ, S1,P1) and G2 = (V2, Ʃ, S2,P2) , Generating L1 and L2, respectively, we show how to construct a new CFG for each of the three cases. 1. Gu = (Vu, Ʃ, Su, Pu) generating L1 U L2 2. Gc= (Vc, Ʃ, Sc, Pc) generating L1L2 3. G* = (V, Ʃ, S, P) generating L1 * Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 51 Grammar 51  Union Gu = (Vu, Ʃ, Su, Pu) A grammar Gu = (Vu, Ʃ, Su, Pu) generating L1 U L2. First we rename the element of V2 if necessary so that V1 ∩ V2= Ø Vu= V1 U V2 U {Su} Where Su is a new symbol not in V1 or V2. Then we let Pu= P1 U P2 U { Su S1 | S2 } On the other hand, if x is derivable from Su in Gu, the first step in any derivation must be SuS1 or SuS2 In the first case, all subsequent productions used must be productions in G1, because no variables in V2 are involved, and thus x∈ L1; in the second case, x ∈ L2. Therefore, L(Gu) ⊆ L1 U L2 Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 52 Grammar 52  Concatenation Gc= (Vc, Ʃ, Sc, Pc) A grammar Gc= (Vc, Ʃ, Sc, Pc) generating L1L2. Again we relabeled variables if necessary so that V1 ∩ V2 = Ø and define Vc = V1 U V2 U {Sc} This time we let Pc= P1 U P2 U { ScS1S2 } If x ∈L1L2 then x = x1x2 , where xi ∈Li for each i. we may then derive x in Gc as follows: Sc S1 S2  *x1 S2  * x1x2 = x First step in the derivation must be ScS1 S2 Where the second step is the derivation of x1 in G1 and the third step is the derivation of x2 in G2. So x ∈ L1L2 Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 53 Grammar 53  Kleene (*) A grammar G* = (V, Ʃ, S, P) generating L 1 * Let V = V1 U {S} Where S ∉ V1.The language L1*contains strings of the form x = x1x2 …xk, where each xi ∈ L1. Since each xi can be derived from S1, then to derive x from S it is enough to be able to derive a string of k S 1‘S. We can accomplish this by including the productions SS1S | ^ In P. Therefore, let P = P1U { SS1S | ^ } The proof that L1 * ⊆ L(G*) is straightforward. If x ∈ L(G*) , on the other hand, then either x = or x can be derived from some string of the form S1k in G*. In the second case, since the only production in G* beginning with S1 are those in G1, we may conclude that x∈ L(G1)k ⊆ L(G1)*. Darshan Darshan Institute Institute of of Engineering Engineering & & Unit Unit –– 3 Theory Theory :: Context 3of of Context Free Free Grammar Computation Computation (2160704) (2160704) 54 Grammar 54  End of Unit - 3 Darshan Darshan Institute Institute of of Engineering Engineering & & Theory Unit Theory Unit 3of –– 3 of Computation :: Context Free (2160704) Free Grammar Computation Context (2160704) 55 Grammar 55