CODEWITHSUNDEEP
c++c++11finite-automataautomata-theory
CiobyMorningStar
CiobyMorningStar

Reputation: 35

NFA to DFA implementation in C++

The title says it all. I need some ideas. The nfa input looks like this and has no epsilon moves.

1 2
0 a 2
1 b 3

etc, meaning that 1 and 2 ar final states and that with 'a' I can get from state 0 to state 2.

I use

struct nod
{
int ns;
char c;
};

vector<nod> v[100];

to save the data, where v[i] is the vector containing all the ways that can go from state i. I need an idea on how to name the new states when there is a multiset of states like

0 a 1
0 a 2
0 a 3

because i can't create state 123 or something like that. And how can i check if a multiset has already been transformed in a state?

Upvotes: 1

Views: 2105

Answers (1)

Patrick87
Patrick87

Reputation: 28292

In the worst case, an NFA with n states will require a DFA with 2^n states: one state for every subset of states in the NFA. Another way to think of this is that all states of the DFA can be labeled with a binary string of length n where the kth bit is set to 1 iff the kth state of the NFA is included in the subset the DFA state corresponds to.

OK, that is possibly a dense explanation to parse. An example will help. Suppose the NFA has states 0, 1 and 2. There are 2^3 subsets of states so our DFA will have up to 8 states. The bit strings are as follows:

  • 000: the empty set, containing no states
  • 001: the set containing only state 0
  • 010: the set containing only state 1
  • 100: the set containing only state 2
  • 011: the set containing states 0 and 1
  • 101: the set containing states 0 and 2
  • 110: the set containing states 1 and 2
  • 111: the set containing all states

We can interpret these bit strings as integers themselves, and this gives us a natural way to label states of the DFA:

  • 0: the empty set, containing no states
  • 1: the set containing only state 0
  • 2: the set containing only state 1
  • 3: the set containing only state 2
  • 4: the set containing states 0 and 1
  • 5: the set containing states 0 and 2
  • 6: the set containing states 1 and 2
  • 7: the set containing all states

The only issue with this ordering is that if you don't end up needing all the states (and frequently you won't), you may have (sometimes large) gaps between states that are used. Your DFA may only really need states 1, 2 and 3 (if your NFA happens to already be a minimal DFA, for instance). Maybe you need states 1 and 7 only. Other possibilities exist.

You can always separate the name and the index for the states you are creating, if you are creating them on demand. If you have created k states and you create a new state as you find you need it, you can assign it index k+1 and name it according to the bit string. That way, your indices are packed densely together and you have traceability back to the subset of NFA states via the name.

I need an idea on how to name the new states when there is a multiset of states like

Name them according to the bit string for the corresponding subset.

And how can i check if a multiset has already been transformed in a state?

Check existing states to see if the bit string for the subset you are encountering has already been used.

Upvotes: 0

Related Questions