1

Although the empty word $\epsilon$ is allowed in context-free grammars, it is always possible to describe any context-free language using a grammar in which the only nullable symbol is the start symbol. Transform the following grammar so that $\epsilon$ is derived only directly from the start symbol $S$ and no other symbols are nullable:

\begin{array}{} S \rightarrow AB \mid cC \\ A \rightarrow Aa \mid \epsilon \\ B \rightarrow bAb \mid b \\ C \rightarrow AAC \mid A\end{array}

I am stuck at the (C) part. This is what I have so far:

\begin{array}{} S \rightarrow ASB \mid cC \mid c \mid SB \mid AS \\ A \rightarrow Aa \mid a \\ B \rightarrow bAb \mid b \\ C \rightarrow CC \mid A\end{array}

Please correct me if I am wrong. Thanks

Jean-Claude Arbaut
  • 23,277
RA20152014
  • 11

1 Answers1

1

What you did with the $A$ productions is fine, but the rest has serious problems; in particular, there’s no reason to have $S\to ASB$, $S\to AS$, or $A\to SB$, and at this stage you should not yet have $S\to c$.

Since $A$ is nullable, every production with $A$ on the right-hand side has to be modified to incorporate the possibility of $A\to\epsilon$. For example, you’ll need $S\to B$ to replace the combination $S\to AB\to B$ using $A\to\epsilon$. After you’ve done this, you can remove the production $A\to\epsilon$, leaving yourself with

$$\begin{align*} &S\to AB\mid B\mid cC\\ &A\to Aa\mid a\\ &B\to bAb\mid bb\mid b\\ &C\to AAC\mid AC\mid C\mid A\mid\epsilon\;, \end{align*}$$

from which you can clearly remove $C\to C$ without losing anything.

Unfortunately, now $C$ is nullable, so you need to repeat the process with $C$. This won’t affect the $A$ and $B$ productions, but it will require adding $S\to c$ to replace the combination $S\to cC\to c$ using $C\to\epsilon$. It will also require modifying the $C$ productions; can you finish it from here?

Brian M. Scott
  • 616,228