__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 :).

## Comments

## Hi, what blogging platform do

Hi, what blogging platform do you use on www.itsalif.info ? I like it and want to start my own blog

Regards

## Currently on Drupal 7.

Currently on Drupal 7.

## It won't work for large

It won't work for large expressions. Doing a GNFA would work for all expressions, but this will only work for simple expressions. But thanks for sharing.

## Hi, Thanks for your

Hi, Thanks for your tutorial!

It's helpful to me!

I would like to translate it into Chinese and post on my blog, it is OK?

## Yes, definitely you can

Yes, definitely you can translate into Chinese :). Although, I would appreciate if you could add a link back to my blog.

Regards,

## Thank You Very Much. This

Thank You Very Much.

This stuff is very helpful for me .

## Thanks sooo much. I have been

Thanks sooo much. I have been trying to figure out how to get regex from NFA and came to your blog. Thank you! Thank you!!!! Also, what did you use to draw the DFA diagrams?

## You are welcome. I have had

You are welcome. I have had the same trouble, and there isn't many tutorials explaining this stuff, so I decided to write one.

I used LaTeX to generate the DFA. The Library I used is vaucanson-g.

http://igm.univ-mlv.fr/~lombardy/Vaucanson-G/

Hope that helps =)

## Add new comment