I know that a regular grammar needs to be of the form:
A -> a
A -> aB, or
A -> λ (lambda)
But I am not sure of the steps needed to create a regular grammar equivalent to the following context-free grammar:
G: S -> BS | AB
A -> Aaa | λ
B -> b
If anyone knows how to go about it, I would appreciate the help :)
Consider the smaller grammar that has only the productions $A\to Aaa\mid\lambda$; it’s easy to see that this grammar generates the language described by the regular expression $(aa)^*$, the language consisting of all strings consisting of an even number of $a$s. Similarly, the grammar that has only the production $B\to b$ generates the one word language $\{b\}$.
Now let’s look at the whole grammar. In any derivation the first production used must be either $S\to BS$ or $S\to AB$. We can apply that first production any number of times, but eventually we’ll have to apply the second one in order to get rid of the $S$. Say we apply $S\to BS$ $n$ times, where $n\ge 0$, and then apply $S\to AB$. Our derivation at that point will look like this:
$$S\Rightarrow^nB^nS\Rightarrow B^nAB\,.$$
Each of those $B$s can do only one thing: turn into a $b$. And the $A$ must produce a string consisting of an even number of $a$s. If the $A$ produces $2m$ $a$s, we end up with $b^na^{2m}b$, where $n$ and $m$ can be any non-negative integers. (Note that it doesn’t matter in what order we turn the $n+1$ $B$s into $b$s and the $A$ into a string of $2m$ $a$s: we always end up with the same result, $b^na^{2m}b$.) Thus, the grammar yields the same language as the regular expression $b^*(aa)^*b$: words that consist of any number of $b$s followed by any even number of $a$s followed by a single $b$. To solve the problem, you need only come up with a regular grammar for this language.