Peter Linz Exercise 3.2

Question

Construct regular expression for the automata given below :

Answer 1

Or,

$$\begin{align*} & A = \epsilon + Bb \quad\qquad \dots (1) \\ & B = Aa + { \color{red}{C}}b \qquad \dots (2) \\ & { \color{red}{C}} = Ba + Ab \qquad \dots (3) \\ \\ \hline \\ &\text{replace C in (2)} \\ &(2) \\ &\Rightarrow B = Aa + \left ( Ba + Ab \right )b \\ &\Rightarrow B = Aa + Bab + Abb \\ &\Rightarrow B = (Aa + Abb)(ab)^{*} \\ &\text{put this value of B in (1)} \\ &\Rightarrow A = \epsilon + (Aa+Abb)(ab)^{*}b \\ &\Rightarrow A = \epsilon + A\left ( (a+bb)(ab)^{*}b \right ) \\ &\Rightarrow A = \left ( (a+bb)(ab)^{*}b \right )^{*} \\ &\Rightarrow \text{Regular Exp} = \left ( (a+bb)(ab)^{*}b \right )^{*} \\ \end{align*}$$

Comments

What I got is

(a(ab)^*b + bbb)^*

is it correct?

---

Hi Debashish.

The first method you used is state elimination method right?

---

(a(ab)^*b + bbb)^* 

wrong ! strings starting with bb are not accepted in this regex. Actually it should be.

Yes it was state elimination. one state at a time.

---

Debashish , i have an idea of state elimination . could you please provide a good link for state elimination?