Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b

Question

geerky42 · Answer

@wio may know. Tagged him, so he will come here when he get on.

anonymous · Answer

With questions like these, sometimes it helps to just construct a formal grammar, and then expand it so that it is regular.

anonymous · Answer

Okay, so we have $a(a+b)^*(ab^*+ba^*)b$.
Let's suppose $T$ represents $a(a+b)^*(ab^*+ba^*)$, then we can start with a rule: $$
\begin{array}{lll}
S &\to& Tb
\end{array}
$$Now we just need to find $T$. 
Again, suppose $C$ represents $a(a+b)^*$.
Consider that $C(ab^*+ba^*)$ is equivalent to $Cab^*+Cba^*$.
First let's construct a means of doing $Cab^*$$$
\begin{array}{lll}
N&\to& Ca \
&|&Nb\
\end{array}
$$Next we need to consider $Cba^*$ and join them:$$
\begin{array}{rcl}
M&\to& Cb\
&|&Ma\
\
T &\to& M \
&|& N 
\end{array}
$$Now finally for $C$.
We've already some something similar before.$$
\begin{array}{lll}
C&\to& a \
&|&Ca\
&|&Cb
\end{array}
$$So now let's just list out the whole grammar:$$
\begin{array}{llll}
S&\to& Tb \
T&\to&M &|& N\
M&\to&Cb&|& Ma\
N&\to&Ca&|& Nb\
C&\to&a&|&Ca &|& Cb
\end{array}
$$Now, I'm using what is called a left regular grammar. That means I will only use rules of the form $\epsilon,a,Na$, where $a$ is a terminal and $N$ is a non-terminal that is also a left regular grammar. A right regular grammar is similar, but instead of $Na$ you have to use rules of the form $aN$. By restricting to these types of rules, you ensure your grammar is regular.