## anonymous one year ago Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b

• This Question is Open
1. geerky42

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

2. anonymous

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

3. anonymous

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.