-1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

Check this for all rules, and you're a step closer to the correct answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ should not it also be E→T∗F∣(E)∣x | E+T $\endgroup$ – webiondev Feb 6 at 23:22
  • $\begingroup$ My reduced form is the following S=E+T |T * F |(E) |x|ε T→T * F |(E) |x E→E+T |T * F |(E) |x F→(E) |x $\endgroup$ – webiondev Feb 7 at 0:06
  • $\begingroup$ @MohammadRahman Yes, sorry, left the obvious bit out :D $\endgroup$ – Luke Mathieson Feb 7 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.