Eliminating epsilon-productions in grammar

Question

I am wondering how to eliminate epsilon-productions in grammar:

 S → S0 
 S → 1
 S → AB
 B → AC
 A → ε
 C → ε

I know that because of C → ε and A → ε we have to rewrite: B → AC as:

 B → A | C | AC

and S → AB as

S → A | B | AB

But production A → ε and C → ε seems to eliminate states A,B and C, leaving only productions:

 S → S0 | 0
 S → 1

Am I correct?

Answer 1

Let me rewrite your grammar a bit into the following grammar.

$\begin{align} S &\rightarrow S0 \; | \; 1 \; | \; AB \\ B &\rightarrow AC \\ A &\rightarrow \varepsilon \\ C &\rightarrow \varepsilon \end{align}$

Let's take the reduction step by step. First we eliminate $C \rightarrow \varepsilon$.

$\begin{align} S &\rightarrow S0 \; | \; 1 \; | \; AB \\ B &\rightarrow A \\ A &\rightarrow \varepsilon \end{align}$

Now we eliminate $A \rightarrow \varepsilon$.

$\begin{align} S &\rightarrow S0 \; | \; 1 \; | \; B \\ B &\rightarrow \varepsilon \end{align}$

Next we eliminate $B \rightarrow \varepsilon$.

$\begin{align} S &\rightarrow S0 \; | \; 1 \; | \; \varepsilon \\ \end{align}$

which is our resulting grammar. Notice that this also makes sense intuitively since we can easily see from the grammar that if we take the rule $S \Rightarrow AB$ as our first derivation step, there is no possibility other than ending up with the empty string $\varepsilon$.