Right-linear grammar from regular expression

989 Views Asked by At

I made a right-linear grammar that from this regular expression:

The alphabet is:

$Σ = \{a, b, c\} $

Regular expression:

$r = cc^*(ba)^*bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $

1

There are 1 best solutions below

2
On BEST ANSWER

You have a problem with the $A$ productions: you can have the derivation

$$S\Rightarrow cA\Rightarrow cbaA\Rightarrow cbacA\Rightarrow cbacB\Rightarrow cbacbb\;,$$

which you clearly don’t want. You need to make sure that once you stop generating $c$’s and generate something else, you never return to generating $c$’s. Why not let $S$ do the work of generating $c$’s, and confine $A$ to generating $ba$ pairs or stopping: $S\to cS\mid cA$, and $A\to baA\mid bb$? We now have

$$\begin{align*} &S\to cS\mid cA\\ &A\to baA\mid bb\;. \end{align*}$$

Any derivation must begin with some number $n$ of applications of $S\to cS$, where $n$ can be $0$, followed by an application of $S\to cA$; at that point we have

$$S\Rightarrow^* c^ncA\;.$$

Now we can only apply $A\to baA$ $m$ times for some $m\ge 0$ and finish off with $A\to bb$, and the result is

$$S\Rightarrow^* c^ncA\Rightarrow^* c^nc(ba)^mbb$$

for any $m,n\ge 0$. This is exactly what your regular expression requires, since $cc^*=c^*c$.