FOR FREE YEAR SOLVED

DFA/NFA to Regular Expression Calculation 

Procedure to find regular expression from a DFA or NFA:

1. Ignore any trap state
2. DFA/NFA treat the same way
3. Resolve the loop
4. If more than one state is final then write RE for each final state and add all.
5. Always take the longest path
6. 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)*