Solved

Converting an NFA to a DFA?

Posted on 2009-05-06
3
943 Views
Last Modified: 2013-11-18
Hi,

I'm trying to figure out how to convert an NFA to a DFA. (I assume people in this topic know what those are, if not let me know I will try to explain).

Making an NFA from a regular expression is ok, I just don't get the process by which you build a DFA from it. I think that you can visit each state of an NFA with every letter in your input alphabet, and tally up all the states you could be in - could someone let me know how to do this, step by step?

Thanks
0
Comment
Question by:DJ_AM_Juicebox
  • 2
3 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 24323552
The idea is to group several NFA states into one DFA state, check the possible next NFA states, group them together into new DFA states, and repeat until all DFA states have been completed.

You start with the initial state(s) of the NFA, and add one state to the DFA that corresponds to that set of states.
For each next symbol of those states (in the NFA), you add an outgoing arrow to the DFA state, and determine the target states for each of them (each of these new DFA states will again correspond to a collection of NFA states).
Repeat this for each of the DFA states identified.

For example, if you have this NFA :

         _0
        / \
        | \/
       -----  1    -----  0    ------
---->| A |---->| B |---->|*C*|
       -----        -----        ------
        | /\
        \_/
          1

(I hope that's clear, but A is the initial state, with 0 and 1 looping back to it, and 1 going to B. From B, 0 is going to C, which is the end state (marked by *'s).

To construct the DFA, you start with the initial state (A) in the NFA, and create a state for it in the DFA : {A} :

       ---------
---->| {A} |
       ---------

In the NFA, the state A allows two next symbols (0 and 1), so in the DFA, we add two outgoing arrows (one for symbol 0, and one for symbol 1). In case of symbol 0, the next state is always A, so in the DFA, that becomes a loopback. In case of symbol 1, the next state is either A or B, so in the DFA, we add a new state {A,B} :

           _0
          / \
          | \/
       ---------  1   -----------
---->| {A} |---->| {A,B} |
       ---------       -----------

State {A} in the DFA is now complete, so we move to state {A,B}. From the states A and B in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 1, the next state is always A, so in the DFA, we add a pointer back to state {A}. In case of symbol 0, the next state is either A or C, so in the DFA, we add a new state {A,C} :

           _0
          / \
          | \/
       ---------  1   -----------  0   -----------
---->| {A} |---->| {A,B} |---->| {A,C} |
       ---------       -----------       -----------
           /\              |
            \_______/
                  1

State {A,B} in the DFA is now complete, so we move to state {A,C}. From the states A and C in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 0, the next state is always A, so in the DFA, that becomes a pointer to state {A}. In case of symbol 1, the next state is either A or B, so in the DFA, that becomes a pointer to state {A,B} :

         _0     ________________0
        / \     /                                \
        | \/  \/                                 |
       ---------  1   -----------  0   -----------
---->| {A} |---->| {A,B} |---->| {A,C} |
       ---------       -----------       -----------
           /\              |     /\              |
            \_______/      \_______/
                   1                    1

State {A,C} in the DFA is now complete, and there are no more states to process. All we have to do now, is mark one or more states in the DFA as end states. In this case, there's only one : {A,C} :

         _0     ________________0
        / \     /                                \
        | \/  \/                                 |
       ---------  1   -----------  0   ------------
---->| {A} |---->| {A,B} |---->|*{A,C}*|
       ---------       -----------       ------------
           /\              |     /\              |
            \_______/      \_______/
                   1                    1


If the sketches in the post aren't clear, here they are again in a fixed width font :
NFA :
 

       _0

      / \

      | \/

     -----  1  -----  0  -----

---->| A |---->| B |---->|*C*|

     -----     -----     -----

      | /\

      \_/

        1
 
 

DFA :
 

      _0    ____________________0

     / \   /                    \

     | \/ \/                    |

     -------  1  ---------  0  ---------

---->| {A} |---->| {A,B} |---->| {A,C} |

     -------     ---------     ---------

         /\       |    /\       |

          \_______/     \_______/

              1             1

Open in new window

0
 

Author Comment

by:DJ_AM_Juicebox
ID: 24350903
Dang, thanks Infinity, works now,

Thanks
0
 

Author Closing Comment

by:DJ_AM_Juicebox
ID: 31578851
bangarang!
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
sum67 challenge 35 93
sumHeights  challenge 17 65
Change to event 1 99
Problem to picture file 20 30
Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

929 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now