0
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$

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.