Weblog of Alif

Exploring the Web: An Apple a day

DFA / NFA to Regular Expression (without using GNFA)

June 29, 2011 -- alif
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).
Several people asked me about the diagrams. They were created using LaTeX. Read here

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:

  1. Create a DFA that contains the substring 010
  2. Complement the DFA and make the NFA from it (to get a NFA that does not contain 010)
  3. 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

Submitted by Selina (not verified) on

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.

Submitted by alif on

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

Regards,

Submitted by Karan Chugh (not verified) on

Thank You Very Much.
This stuff is very helpful for me .

Submitted by Frank (not verified) on

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?

Add new comment