CNF & Leftmost Derivation - Theory of Computation

Theory of Computation- Chomsky Normal Form & Leftmost Derivation - 1CNF - 2CNF - 3CNF - BCNF and Examples

1. CHOMSKY NORMAL FORM (CNF) & LEFTMOST DERIVATION (LMD) MADE BY: DIMPY CHUGH(1833) DRISHTI BHALLA(1838)

2. DEFINITION If a Context Free Grammar or CFG has only productions of the form Nonterminal -> string of exactly two n on-terminals or Nonterminal -> one terminal then, it is said to be in Chomsky Normal Form, CNF. Example: S → AS | a A → SA | b

3. STEPS FOR CONVERSION The conversion to Chomsky Normal Form has four main steps: 1. Get rid of all λ -Productions . 2. Eliminate Non-terminal Unit Productions. A → B , B → b A → b 3. Elimination of more than one terminals by a non- terminal in a production. 4. Replace every production that is too long by shorter productions. A → BCD A → BE E → CD

4. THEOREM-1 STATEMENT- If L is a language generated by some CFG, then there is another CFG that generates all the non- λ words of L, all of whose productions are of one of two basic forms: Nonterminal-> string of only Non-terminals or Nonterminal -> one terminal PROOF- Let us start with the CFG- S -> X1 | X2aX2 | aSb | b Xl -> X2X2 | b X2 -> aX2 | aaX1 Now, in order to convert it into the above form , we introduce new productions : A -> a and B -> b

5. After conversion we have , S -> X1 X1 -> X2X2 S -> X2 A X2 X1 -> B S -> A S B X2 -> A X2 S -> B X2 -> AA X1 Thus, we have converted the original CFG into the desired form.

6. STATEMENT - For any context- free language L, the non- λ words of L can be generated by a grammar in which all the productions are in CNF. PROOF - Let our initial CFG is S -> XI X2 X3 X8 S -> X3 X5 S -> b Now, in order to get the given CFG in CNF form we’ll add certain new non-terminals , i.e. S -> XI X2 X3 X8 S -> XI R1 R1 -> X2 X3 X8 R1 -> X2 R2 R2 -> X3 X8 THEOREM-2

7. Consider another CFG X -> X1aX2bX3 Apply Theorem 1 and add productions A->a and B->b to get string of solid non-terminals. Now, X -> X1 A X2 B X3 X -> X1R1 R1 -> AX2BX3 R1 -> AR2 R2 -> X2BX3 R2 -> X2R3 R3 -> BX3 In this way, we have converted the long productions with long strings of non-terminals into sequences of productions with exactly 2 non-terminals on RHS. Thus, the new grammar in CNF generates the same language as the old grammar.

8. Ques16 i). T he following CFG has unit productions. C onvert the following CGF into CNF. S -> X X - > Y Y- > Z Z -> aa Sol16). S -> X - > Y => S -> Y S -> Y -> Z => S -> Z S -> Z -> aa =>S ->aa Since S->aa is not in CNF , we introduce a new production A->a to transform it to CNF. Thus, the new grammar in CNF form is : A -> a S -> AA QUESTIONS

9. Ques14 v). Convert the following CGF into CNF . S -> ABABAB A -> a| λ B -> b| λ Sol13). Removing λ productions, A -> a ---------1 B -> b ---------2 S -> ABABAB Using Theorem 2, S -> AR1 ---------3 R1 -> BABAB R1 -> BR2 ---------4 R2 -> ABAB R2 -> AR3 ---------5 R3 -> BAB R3 -> BR4 ---------6 R4 -> AB ---------7 Thus, the new grammar in CNF form comprises of (1,2,3,4,5,6,7).

10. Ques14 iv). Convert the following CGF into CNF. E -> E + E E -> E*E E -> ( E) E -> 7 The terminals here are +, *, (, ), 7. Sol12). E -> 7 --------------1 Using Theorem 1, we add new productions that will help in converting CGF to CNF. F -> + --------------2 G -> * --------------3 H- > ( --------------4 I -> ) --------------5 Now , we have E -> EFE E -> ER1 --------------6 R1 -> FE --------------7 E -> EGE E -> ER2 --------------8 R2 -> GE --------------9 E -> HEI E -> HR3 -------------10 R3 -> EI -------------11 Thus, the new grammar in CNF form comprises of ( 1,2,3,4,5,6,7,8,9,10,11).

11. LEFT MOST DERIVATIONS The leftmost non-terminal in a working string is the first non-terminal that we encounter when we scan the string from left to right. For example : In the string abNbaXYa , the leftmost nonterminal is N . If a 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 string, then this derivation is called a leftmost derivation .

12. Ques17 i)Find the leftmost derivation for the word “ abba ” in the grammar: S -> AA A -> aB B -> bB | λ Sol18)( i ). The following is a leftmost derivation: S -> A A S -> a B A S -> ab B A S -> abb B A S -> abb λ A S -> abba B S -> abba λ S -> abba QUESTIONS

13. Ques17 ii) Find the leftmost derivation for the word “ abbabaabbbabbab ” in the CFG: S-> SSS|aXb X-> ba|bba|abb Sol18)(ii). The following is a leftmost derivation: S -> S SS S -> a X bSS S -> abbab S S S -> abbaba X bS S -> abbabaabbb S S -> abbabaabbba X b S -> abbabaabbbabbab

14. ADVANTAGES.. CNF Grammar can be used to determine whether a string is a member of the language associated with it or not . It can be used to find the no. of production steps required to generate a string. The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters has exactly 2 n − 1 steps. Example : S -> AX|AB A -> a X -> SB B -> b The string to be generated is “ aabb ” having n(no. of letters in a string ) =4. The following is a leftmost derivation: S -> A X S -> a X S -> a S B S -> a A BB S -> aa B B S -> aab B S -> aabb Here, A string of n(n=4) letters has exactly 2n-1(2*4-1=7) steps .

15. THANK YOU !!!