2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have never seen these steps. I follow a procedure similar to the one in the answer here: cs.stackexchange.com/questions/18316/… $\endgroup$ – hb20007 Apr 5 '17 at 11:06
  • $\begingroup$ The answer there, by the way, also ends up with a "useless" symbol. Is it the correct thing to eliminate this kind of productions? $\endgroup$ – hb20007 Apr 5 '17 at 11:08
  • 1
    $\begingroup$ It depends on your procedure, as I wrote it may change. These steps are based to the textbook Introduction to Automata Theory, Languages, and Computation Ullman and Hopcroft $\endgroup$ – abc Apr 5 '17 at 11:09
  • $\begingroup$ You said that cleaning the grammar takes place before converting to CNF. However, before converting to CNF it is not clear that S will become an unreachable variable. It only becomes unreachable after the conversion. So what should be done now? $\endgroup$ – hb20007 Apr 5 '17 at 11:11
  • $\begingroup$ You answered my question after editing your answer $\endgroup$ – hb20007 Apr 5 '17 at 11:25

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.