So I have to convert the following grammar to CNF. However in order for me to do so, I know I will have to first:
i) eliminate the recursive start symbol
ii) eliminate null-rules to construct an essentially non-contracting
grammar
iii) eliminate unit rules
S -> SS
S -> aSb
S -> 1
But I am so lost and this is my first time working with coversions to CNF. I know the basic principals on converting the grammar, but whats getting me confused is the above transformations that I have to do first. Can someone please show me how i would do this.
Step by step:
(i) Eliminate the recursive start symbol. This is very easy: just introduce a new symbol $S'$, replace $S$ by $S'$ in the rules, and add the rule $S\to S'$. This give the following grammar: $$\begin{equation}\begin{split} &S &\to S' \\ &S' &\to S'S' \\ &S' &\to aS'b \\ &S' &\to 1 \end{split}\end{equation}$$
(ii) The grammar has no null rules (aka "empty productions").
(ii.5) Ensure that every rule has at most one terminal symbol. Do this by introducing a nonterminal $U_x$ for each terminal $x$, and adding a rule $U_x\to x$. For each occurrence of $x$ in a rule whose RHS has length at least $2$, replace $x$ with $U_x$. Transforming the given grammar in that way gives: $$\begin{equation}\begin{split} &S &\to S' \\ &S' &\to S'S' \\ &S' &\to U_aS'U_b \\ &U_a&\to a \\ &U_b&\to b \\ &S' &\to 1 \\ \end{split}\end{equation}$$
(iii) Now, the only unit rule is $S\to S'$, but that can't be eliminated.