# Convert CFG to CNF Arithmatic Expression

Convert CFG to CNF

The Grammar

E→E+T
E→T
T→T*F
T→F
F→(E)
F→x


Step 1 Assign variables to terminals

A→ +
B→ *
C→(
D→ )
F→x


Step 2

Remove epsilon which in this grammar is not available


Step 3

Remove useless symbols which there are none


Step 4 Remove unit rule

S→E
E→T
T→F
So we have
E→T*F|E+T
T→(E)|x
F→(E)|x


Step 5 Add a start symbol

    S→T*F|E+T
E→T*F|E+T
T→(E)|x
F→(E)|x
A→ +
B→ *
C→(
D→ )
F→x


Step 6 Convert in the form A→BC and A→a Until now we have

S→T*F|E+T
E→T*F|E+T
T→(E)|x
F→(E)|x
A→ +
B→ *
C→(
D→ )
F→x


Using terminal variables we get

S=EAT|TBF
T→CED|x
E→EAT|TBF
F→CED|x
A→ +
B→ *
C→(
D→ )
Let
A_1=AT
B_1=BF
E_1=ED


So final CNF is

S=EA_1 |TB_1
T→CE_1 |x
E→EA_1 |TB_1
F→CE_1  | x
A→ +
B→ *
C→(
D→ )
F→x
A_1=AT
B_1=BF
E_1=ED


But after converting I cannot deduce this string from gammar

(((x+(x)∗x)∗x)∗x)


THanks Rahman

The mistake is in step 4. You need to do it progressively, in particular $$E\rightarrow T$$ is not just replaced with $$E\rightarrow T\ast F$$, but by all possible things that $$T$$ can be replaced by. In this case, that includes the rule $$T \rightarrow F$$. So the unit rule gets propagated to $$E \rightarrow F$$, which then has to be replaced in turn giving $$E \rightarrow T \ast F \mid (E) \mid x$$.