0

I have to convert the below grammar to GNF.

$S \Rightarrow SA$

$A \Rightarrow aAb|cCc$

$B \Rightarrow D|ba$

$C \Rightarrow dCd| ɛ$

$D \Rightarrow De|Df|cD|c$

I have seen some examples and tutorials on the internet. In most of them, there were 3 steps for converting a CFG to GNF, and the first one was converting to CNF. Also, it was said that if $S$(initial state) appears in RHS we have to add a new state such as $S'$ and add $S' \Rightarrow S$ to our productions(actually I don't know its reason). I have converted the grammar to CNF after eliminating ɛ productions, adding some new productions to my grammar, and here is my new grammar which is in CNF form, and I think it is correct: $S'\Rightarrow SA$ , $V_1 \Rightarrow AT_b$

$S \Rightarrow SA$ , $V_2 \Rightarrow CT_c$

$A \Rightarrow T_a|V_2|T_cT_c$, $V_3 \Rightarrow CT_d$

$B \Rightarrow DT_e|DT_f|T_cD|c|T_bT_a$, $T_a \Rightarrow a$, $T_b \Rightarrow b$

$C \Rightarrow T_dV_3|T_dT_d$, $T_c \Rightarrow c$, $T_d \Rightarrow d$, $T_e \Rightarrow e$

$D \Rightarrow DT_e|DT_f|T_cD|c$, $T_f \Rightarrow f$

But in the next step, for eliminating left recursion and ɛ productions, my solution becomes complicated, and I think I'm not doing the right thing. Is there a better way or maybe a hint or idea to solve this question? I did not write my whole steps in description, because I think it just makes this question longer.

Aylin Naebzadeh
  • 1

1 Answers1

0

Well, there is no need to convert our grammar to CNF, and it can just make our solution more complicated. And also the first step, which was adding the new production rule with $S'$, was not necessary either. These are the steps for converting a CFG to GNF:

  1. Remove all nullable productions.
  2. Remove all unit productions.
  3. Eliminate left-recursions.
  4. If the RHS of a production starts with a variable, then replace it.
Aylin Naebzadeh
  • 1