DFA and NFA

This is a discussion on DFA and NFA within the C++ Programming forums, part of the General Programming Boards category; What is the best data structure to implement NFA and DFA, or these two needs to be represented in diffrent ...

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    134

    DFA and NFA

    What is the best data structure to implement NFA and DFA, or these two needs to be represented in diffrent data structure for efficiency? I am actually trying to convert NFA to DFA, then check weather a particular string is accepted by DFA OR NOT.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    2,138
    First of all, please post some code to show where you're having trouble. second, explain what DFA and NFA are.

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    134

    I have not started yet, only planning for now

    NFA= Non-deterministic Finite Automata
    DFA= Deterministic Finite Automata

    without knowing what kind of datasructure is good for such things, I can't proceed, I must get a good idea of what can be use to make it an efficient progrmming.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    Quote Originally Posted by kapil1089thekin View Post
    NFA= Non-deterministic Finite Automata
    DFA= Deterministic Finite Automata

    without knowing what kind of datasructure is good for such things, I can't proceed, I must get a good idea of what can be use to make it an efficient progrmming.
    That's the wrong approach, IMO. Focus on the algorithm and the necessary data structures will naturally follow.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21