How many variables does the following grammar have when converted to CNF?

Question

E -> E+T

E -> T

T -> (E)

T -> i

Comments

is there a way to do such questions?

Answer 1

E -> ET’ / i
T’ -> PT
P -> +
E -> RE’
R -> (
E’ -> ES
S -> ) 
T -> RE’
T -> i

Here the key point is E->T so don't take it T epsilon. Simply take E-->(E) hence we can solve this.

Total {E,T',P,R,E'S,T} 7 variables.

Comments

hii @Ashwin

construction to CNF should never loss any strings, in your case atleast '( i )' and 'i' are lost

first remove unit production from above grammer you will get new grammer as,

E->E+T / (E) / i

T->(E)

T->i

now convert above grammer to CNF, you will get,

E->E'T / SR / i

T->SR / i

S->PE

E'->EM

P->(

R->)

M->+

total 7 non terminals and 4 terminals

---

Then why we cannot add

E--> i directly??

This will give exact result.

---

yes, i have added E--> i directly.

---

@joshi_nitish Hello, I'm saying in my result by adding E --> i, everything will be correct.

And production for P is missing in your CNF form.

And something is redundant as well . please can you check your CNF deduction again?

---

yes, something was redundant. thankyou.

---

i have already added E->i in your grammer. you readded it, now i removed it. :P

---

Hi thanks for ur analysis.

So if a cfg is to be converted to cnf, We should remove null production and unit productions.  As they will be a problem while converting.

Is it true?

---

Yes @gari. and CNF grammar should not contain null productions.

@joshi_nitish Infact I didn't know you can edit our answers :p haha.

---

Thanks @Ashwin :)