1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

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