0
$\begingroup$

I would like to delete the $\epsilon$-production from the context free grammar with the following rules P:

$$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$

Now we were only given this algorithm for that task:

  1. collect all variables from which the empty word is derivable.

-> which in this case is only S

  1. Add to the new rules P' every rule $A \rightarrow \alpha'$, with $\alpha \neq \epsilon$, for which P had a rule $A \rightarrow \alpha$, so that $\alpha'$ results from $\alpha$ by erasing all variables that were collected in step 1.

In this case I would erase $S \rightarrow \epsilon$ and since P included $A \rightarrow aS$ I would add $A \rightarrow a$ to P', giving me:

$$S \rightarrow ASB , BSA$$ $$A \rightarrow a$$ $$B \rightarrow bB, b$$

The grammar with these rules does not, however yield the same language as P, in fact the S never disappears. Can anybody please tell me what I'm doing wrong and how to do it correctly?

$\endgroup$
5
$\begingroup$

You cannot erase the $ϵ$-production from this grammar and keep the same language. The reason is that since you have the production $S\to ϵ$, the language contains $ϵ$. And the only way a CF language can contain $ϵ$ is with an $ϵ$-production.

$\endgroup$
  • $\begingroup$ Thank you. Would I be able to reproduce $L(G)-\{\epsilon\}$, where G is the original grammar, without $S \rightarrow \epsilon$? $\endgroup$ – eager2learn Feb 16 '15 at 15:08
  • 2
    $\begingroup$ Yes. You can always do that (see beginning of CNF conversion). You indeed collect all variables deriving on $ϵ$. Then for any production $X\to\xi$, you take each combination of occurences of these variables in $\xi$ and make a new production by erasing them. You add these new productions to the grammar, and you remove the $ϵ$-productions. $\endgroup$ – babou Feb 16 '15 at 15:58
0
$\begingroup$

Keep the old productions, you add new rules. Some occurrences of $S$ may lead to a nonempty string while other occurrences might lead to nothing, so you need both old and new in general.

Also erase $S$ from the right hand side of productions for $S$ itself.

Thus the new rules now are

$$S \rightarrow ASB , BSA, AB , BA$$ $$A \rightarrow aS, a$$ $$B \rightarrow bB, b$$

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