__Procedure to find regular expression from a DFA or NFA:__

- Ignore any trap state
- DFA/NFA treat the same way
- Resolve the loop
- If more than one state is final then write RE for each final state and add all.
- Always take the longest path
- Reduce the number of states if possible

__Step1__:** ****Ignore any trap state at time of find regular expression from DFA/NFA**

Here is an example where we **ignore the trap state** ${\mathbf{q}}_{\mathit{t}}$.

__Step2__:** ****Whatever the machine DFA or NFA we follow the same procedure to find regular expression****.**

__Step3__:** **__Resolve Loop__

**We can resolve the loop in two ways –**

a. **Left hand side loop resolve **and b.** Right hand side loop resolve.**

**a. Left hand side loop resolve: **(Here we calculate loop left to right)

We start from the initial state ‘**A****’** and again come back to left hand side **state ‘A****’ **by traversing all states several times. And as we know we always take the longest path so, here it is **(pq)*****. **

Now we reach left hand side at **state ‘A****’ **using the longest path **(pq)*****. **

After reached left hand side at **state ‘A’**** **how we go to the final **state ‘B’**?

Simply we go to left hand side **state ‘A’** to the final **state ‘B’** by input **p**.

So, the final regular expression of machine M is **RE1 = (pq)*p**

**b. Right hand side loop resolve: **(Here we calculate loop right to left)

Unlike left hand loop resolve, we first go initial **state ‘A’**** **to right hand final **state ‘B’**** **simply by input **p****.**

**So, the final regular expression for machine M is ****RE2 = p(qp)***** **

**So, machine M has two regular expressions one from left hand loop resolve and one from right hand side. **

**As we know one machine can have more than a regular expression but all are equivalent.**

But another way we can say this two regular expression is equivalent because **regular expression holds the associative property**.

__Step 4:__** **__More than one final state__

This machine has two **final states ‘A’ and ‘B’**.

So, we calculate regular expressions individually for the **state ‘A’** and **state ‘B’**.

Regular expression of **final state ‘A’**= **(pq)***

Regular expression of **final state ‘B’** = **(pq)*p** **(Left hand side loop resolve).**

**After calculating the individual regular expression of final states just add all.**

**So, final regular expression for this machine RE = ****(pq)* + (pq)*p = (pq)* (λ + p)**** **

**Step 5:**** **__Always take the longest path__

We always try to choose the longest path to cover all possible states when we calculate regular expression.

**Machine**:** **${\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{\omega}\mathbf{\right)}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{2}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}$**i.e. Odd numbers of b’s**

Now we calculate the **regular expression **of this machine by **left hand side loop resolve.**

As we know to calculate this regular expression by **left hand side loop resolve **we will reach the first left hand side state ${\mathbf{q}}_{\mathbf{0}}$ from initial same state by traversing all states of the machine i.e. **we always consider the longest loop to calculate the path**.

But this longest loop is **not** like **(a*ba*b)***

**To reach left hand side state **${\mathbf{q}}_{\mathbf{0}}$ from the initial same state by longest loop: **(a + b a* b)***

If you do not understand follow the machine how many ways you reach left hand side state ${\mathbf{q}}_{\mathbf{0}}$ from the initial same state:

i. By input **‘a’** (loop: **a***) we reach ${\mathbf{q}}_{\mathbf{0}}$ from the initial same state.

**OR (+)**

ii. By input **ba*b** we reach ${\mathbf{q}}_{\mathbf{0}}$ from the initial same state. As we know the same path we repeat several times to get ${\mathbf{q}}_{\mathbf{0}}$, so, longest path **(b a* b)***.

**OR (+)**

iii. We can also get ${\mathbf{q}}_{\mathbf{0}}$ from the initial same state by a combination of **a*** and **(b a* b)***.

So, the final path to ${\mathbf{q}}_{\mathbf{0}}$ is **(a + b a* b)***** **i.e. **either** we can get ${\mathbf{q}}_{\mathbf{0}}$ by using **a***** ****OR** it can get by **(b a* b)***** ****OR** combination of both.

Now, after we reached ${\mathbf{q}}_{\mathbf{0}}$ from initial same state, we go to the final state ${\mathbf{q}}_{\mathbf{1}}$ by input **ba***.

So, final **regular expression** of given machine = **(a + b a* b)*ba***** **(Left hand side loop resolve)

So, the final **regular expression** of given machine = **ba*(a + b a* b)***** **(Left hand side loop resolve)

**Step 6:**** **__Reduce the number of states__

Let take a machine as an example and reduce the number of machine.

Now we start from the last state ${\mathbf{q}}_{\mathbf{3}}$ to resolve it.

We can resolve ${\mathbf{q}}_{\mathbf{2}}$ now,

After more simplification of state ${\mathbf{q}}_{\mathbf{1}}$

So, the final **regular expression ****RE = a(a + a(b + ba)*b)***