The general approach to get a Regular expression (regex) from DFA/NFA is to convert a DFA to a GNFA by reducing states. Read more on wikipedia. However, for __not too complicated__ DFA, it is often easier to get a regex from NFA instead of going through GNFA (which btw makes regex big).

For regex, the patterns that contains a substring, it is easy to write a regex. Lets say you have to write a regex for all strings that contains the string 010, where: ∑ = {0, 1}. Such cases are straight-forward. A regex would be:

(0 U 1)* 010 (0 U 1)*

But consider the following:

Write a regex for strings that **does not contain** substring 010. Where ∑ = {0, 1}.

It is not straight-forward. For such case, it is often easier to draw a DFA, then make NFA, and then get regex from it (without using GNFA approach).

Here’s one approach to solve such problem. The following steps are used:

- Create a DFA that contains the substring 010
- Complement the DFA and make the NFA from it (to get a NFA that does not contain 010)
- Get the Regex from it

Step #1: Creating the DFA that contains 010

Step #2: Complement the previous DFA (i.e. change the old accept state as reject state, and non-accept state as accept state). And, remove the unnecessary ‘d’ state to get the NFA.

Step #3: Now, we write the regex. There are several ways to do it, however, I use the following technique:

– From start state (a): You can either take **1** or **00*11** to come back to the start state (**a**), and repeat it.

So the first part of regex looks like following:

(1 U 00*11)*

– After reading the previous input sequence, you are still in start state (a). You can either end it there (as **a** is an accepting state). OR you can read __00*__ to get to State **b** to end it there, OR you read __00*1__ and reach State **c** and end it there.

So the complete regex looks like the following:

(1 U 00*11)* (ε U 00* U 00*1)

Thats about it. I hope it helps out someone :).