Conversion of CFG to CNF.pptx

This slide describes the conversion of CFG to CNF.
CFG stands for context free grammar.
CNF stands for Chomsky Normal Form
It is type-2 grammar.
It is accepted by push down automata.
Every CNF is generated from CFG

1. Conversion of Cfg into cnf By, Rishikesh

2. AGENDA What is cfg ? What is cnf ? Solving a problem

3. CFG CFG stands for Context Free Grammar. It is a type-2 Grammar. The productions can be of the form, α -> β | α |<=| β | α ∈ V | α |=1 β ∈ (V ∪ T) CFG contains the following four components, G=(V,T,P,S) Example: S-> aSb S->ab Presentation Title 3

4. CNF CNF stands for Chomsky Normal Form Every CFL is generated by a CFG, in which all productions are of the form, A->BC A->a Where A,B,C – Variables and a – Terminal. This form of CFG is CNF. In order to find the CNF, the following operations are to be performed, Eliminate use-less symbols, Eliminate ε -production, Eliminate unit production. Presentation Title 4

5. Presentation Title 5 1.Consider the grammar ({S,A,B},{ a,b },P,S) has the productions, S-> bA|aB A-> bAA|aS|a B-> aBB|bs|b Solution: Step-1: Find the productions which are already in CNF: A->a B->b Step-2: Replace the terminals on the right by new variables: ( i ) S-> bA S-> ->b  

6. Presentation Title 6 Step-2: Replace the terminals on the right by new variables: (ii) S-> aB S-> ->a (iii) A-> bAA A-> AA ->b This is not in CNF form (iv)A-> aS A-> ->a (v) B-> aBB B-> BB ->a This is not in CNF form  

7. Presentation Title 7 Step-2: Replace the terminals on the right by new variables: (vi) B-> bS B-> S ->b   Step-3: According to CNF Theorem, the (RHS) body should contain only two variables: A-> A-> ->AA ->b   (ii) B-> B-> ->BB ->a  

8. Final ANSWER: Thus the resultant productions in cnf are, Presentation Title 8 S-> A| B A-> S| B-> S| |b ->a ->b ->AA ->BB  

9. THANK YOU Presented by, RISHIKESH B 811720104084 Presentation Title 9