Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?

Question

I have an example below which seems to lead to a “useless” production.

This is the original grammar:

\begin{align*} S&\longrightarrow aX\,|\,Yb\\ X&\longrightarrow S\,|\,\varepsilon\\ Y&\longrightarrow bY\,|\,b \end{align*}

Here is the conversion to CNF:

Step 1: Make sure the start symbol does not occur on the RHS. \begin{align*} S'\!\!\!&\longrightarrow S\\ S&\longrightarrow aX\,|\,Yb\\ X&\longrightarrow S\,|\,\varepsilon\\ Y&\longrightarrow bY\,|\,b \end{align*} Step 2: Remove rules that lead to $ \varepsilon $. \begin{align*} S'\!\!\!&\longrightarrow S\\ S&\longrightarrow a\,|\,aX\,|\,Yb\\ X&\longrightarrow S\\ Y&\longrightarrow bY\,|\,b \end{align*} Step 3: Remove all unit productions. \begin{align*} S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\ S&\longrightarrow a\,|\,aX\,|\,Yb\\ X&\longrightarrow a\,|\,aX\,|\,Yb\\ Y&\longrightarrow bY\,|\,b \end{align*} Step 4: Remove remaining productions which do not conform to CNF. \begin{align*} S'\!\!\!&\longrightarrow a\,|\,AX\,|\,YB\\ S&\longrightarrow a\,|\,AX\,|\,YB\\ X&\longrightarrow a\,|\,AX\,|\,YB\\ Y&\longrightarrow BY\,|\,b\\ A&\longrightarrow a\\ B&\longrightarrow b\\ \end{align*}

It seems that following the algorithm has led to a useless production. The second production will never be invoked from the starting symbol.

Is the production really useless and is it right to remove it from the Chomsky Normal Form grammar?

Answer 1

Given a $CFG \ G$, before converting in $CNF$ you need to clean the grammar, that means (order is important):

1) eliminate $\epsilon$-productions

2) eliminate unit productions

3) eliminate variables that do not derive terminal strings

4) eliminate unreachable variables from the starting symbol

After this you make substitutions/split rules in order to obtain a CNF grammar.

According to these rules, after your step 3 I would eliminate non generating variables (all the variables can reach a terminal string) and unreachable variables (You cannot reach $S'$ from $S$), to end up with the following productions:

\begin{align*} S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\ \ X&\longrightarrow a\,|\,aX\,|\,Yb\\ Y&\longrightarrow bY\,|\,b \end{align*}

I don't know which procedure you are following (it may vary according to textbooks/instructors), but if you don't apply steps $3$ and $4$ then yes, you could end up with useless symbols in your grammar in CNF.