NFA to DFA Conversion in C++

This is a C++ Program to convert NFA to DFA. A DFA (Deterministic Finite Automaton) is a finite state machine where from each state and a given input symbol, the next possible state is uniquely determined. On the other hand, an NFA (Non-Deterministic Finite Automaton) can move to several possible next states from a given state and a given input symbol. However, this does not add any more power to the machine. It still accepts the same set of languages, namely the regular languages. It is possible to convert an NFA to an equivalent DFA using the powerset construction.
The intuition behind this scheme is that an NFA can be in several possible states at any time. We can simulate it with a DFA whose states correspond to sets of states of the underlying NFA.

Here is source code of the C++ Program to Construct DFA from NFA. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <cstdio>
```
```
#include <fstream>
```
```
#include <iostream>
```
```
#include <bitset>
```
```
#include <vector>
```
```
#include <cstring>
```
```
#include <cstdlib>
```
```
#include <algorithm>
```
```
#include <queue>
```
```
#include <set>
```
```
#define MAX_NFA_STATES 10
```
```
#define MAX_ALPHABET_SIZE 10
```
```
using namespace std;
```
```
// Representation of an NFA state
```
```
class NFAstate
```
```
{
```
```
    public:
```

        int transitions[MAX_ALPHABET_SIZE][MAX_NFA_STATES];

```
        NFAstate()
```
```
        {
```

            for (int i = 0; i < MAX_ALPHABET_SIZE; i++)

                for (int j = 0; j < MAX_NFA_STATES; j++)

                    transitions[i][j] = -1;

```
        }
```
```
}*NFAstates;
```
```
// Representation of a DFA state
```
```
struct DFAstate
```
```
{
```
```
        bool finalState;
```

        bitset<MAX_NFA_STATES> constituentNFAstates;

        bitset<MAX_NFA_STATES> transitions[MAX_ALPHABET_SIZE];

        int symbolicTransitions[MAX_ALPHABET_SIZE];

```
};
```
```
set<int> NFA_finalStates;
```
```
vector<int> DFA_finalStates;
```
```
vector<DFAstate*> DFAstates;
```
```
queue<int> incompleteDFAstates;
```

int N, M; // N -> No. of stattes, M -> Size of input alphabet

// finds the epsilon closure of the NFA state "state" and stores it into "closure"

void epsilonClosure(int state, bitset<MAX_NFA_STATES> &closure)

```
{
```

    for (int i = 0; i < N && NFAstates[state].transitions[0][i] != -1; i++)

        if (closure[NFAstates[state].transitions[0][i]] == 0)

```
        {
```

            closure[NFAstates[state].transitions[0][i]] = 1;

            epsilonClosure(NFAstates[state].transitions[0][i], closure);

```
        }
```
```
}
```

// finds the epsilon closure of a set of NFA states "state" and stores it into "closure"

void epsilonClosure(bitset<MAX_NFA_STATES> state,

        bitset<MAX_NFA_STATES> &closure)

```
{
```
```
    for (int i = 0; i < N; i++)
```
```
        if (state[i] == 1)
```
```
            epsilonClosure(i, closure);
```
```
}
```

// returns a bitset representing the set of states the NFA could be in after moving

```
// from state X on input symbol A
```

void NFAmove(int X, int A, bitset<MAX_NFA_STATES> &Y)

```
{
```

    for (int i = 0; i < N && NFAstates[X].transitions[A][i] != -1; i++)

        Y[NFAstates[X].transitions[A][i]] = 1;

```
}
```

// returns a bitset representing the set of states the NFA could be in after moving

// from the set of states X on input symbol A

void NFAmove(bitset<MAX_NFA_STATES> X, int A, bitset<MAX_NFA_STATES> &Y)

```
{
```
```
    for (int i = 0; i < N; i++)
```
```
        if (X[i] == 1)
```
```
            NFAmove(i, A, Y);
```
```
}
```
```
int main()
```
```
{
```
```
    int i, j, X, Y, A, T, F, D;
```
```
    // read in the underlying NFA
```
```
    ifstream fin("NFA.txt");
```
```
    fin >> N >> M;
```
```
    NFAstates = new NFAstate[N];
```
```
    fin >> F;
```
```
    for (i = 0; i < F; i++)
```
```
    {
```
```
        fin >> X;
```
```
        NFA_finalStates.insert(X);
```
```
    }
```
```
    fin >> T;
```
```
    while (T--)
```
```
    {
```
```
        fin >> X >> A >> Y;
```
```
        for (i = 0; i < Y; i++)
```
```
        {
```
```
            fin >> j;
```

            NFAstates[X].transitions[A][i] = j;

```
        }
```
```
    }
```
```
    fin.close();
```
```
    // construct the corresponding DFA
```
```
    D = 1;
```
```
    DFAstates.push_back(new DFAstate);
```

    DFAstates[0]->constituentNFAstates[0] = 1;

    epsilonClosure(0, DFAstates[0]->constituentNFAstates);

```
    for (j = 0; j < N; j++)
```

        if (DFAstates[0]->constituentNFAstates[j] == 1 && NFA_finalStates.find(

                j) != NFA_finalStates.end())

```
        {
```

            DFAstates[0]->finalState = true;

            DFA_finalStates.push_back(0);

```
            break;
```
```
        }
```
```
    incompleteDFAstates.push(0);
```

    while (!incompleteDFAstates.empty())

```
    {
```

        X = incompleteDFAstates.front();

```
        incompleteDFAstates.pop();
```
```
        for (i = 1; i <= M; i++)
```
```
        {
```

            NFAmove(DFAstates[X]->constituentNFAstates, i,

                    DFAstates[X]->transitions[i]);

            epsilonClosure(DFAstates[X]->transitions[i],

                    DFAstates[X]->transitions[i]);

```
            for (j = 0; j < D; j++)
```

                if (DFAstates[X]->transitions[i]

                        == DFAstates[j]->constituentNFAstates)

```
                {
```

                    DFAstates[X]->symbolicTransitions[i] = j;

```
                    break;
```
```
                }
```
```
            if (j == D)
```
```
            {
```

                DFAstates[X]->symbolicTransitions[i] = D;

                DFAstates.push_back(new DFAstate);

                DFAstates[D]->constituentNFAstates

                        = DFAstates[X]->transitions[i];

```
                for (j = 0; j < N; j++)
```

                    if (DFAstates[D]->constituentNFAstates[j] == 1

                            && NFA_finalStates.find(j) != NFA_finalStates.end())

```
                    {
```

                        DFAstates[D]->finalState = true;

                        DFA_finalStates.push_back(D);

```
                        break;
```
```
                    }
```

                incompleteDFAstates.push(D);

```
                D++;
```
```
            }
```
```
        }
```
```
    }
```
```
    // write out the corresponding DFA
```
```
    ofstream fout("DFA.txt");
```

    fout << D << " " << M << "\n" << DFA_finalStates.size();

    for (vector<int>::iterator it = DFA_finalStates.begin(); it

            != DFA_finalStates.end(); it++)

```
        fout << " " << *it;
```
```
    fout << "\n";
```
```
    for (i = 0; i < D; i++)
```
```
    {
```
```
        for (j = 1; j <= M; j++)
```

            fout << i << " " << j << " "

                    << DFAstates[i]->symbolicTransitions[j] << "\n";

```
    }
```
```
    fout.close();
```
```
    return 0;
```
```
}
```

Output:

$ g++ NFAtoDFA.cpp
$ a.out
 
Input file
NFA.txt
4 2
2 0 1
4
0 1 2 1 2
1 1 2 1 2
2 2 2 1 3
3 1 2 1 2
 
Output file
DFA.txt
4 2
3 0 1 3
0 1 1
0 2 2
1 1 1
1 2 3
2 1 2
2 2 2
3 1 1
3 2 2
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

» Next - C++ Program to Search for an Element in a Binary Search Tree

Related Posts:

Check Computer Science Books
Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Programming Books
Check Data Structure Books

Recommended Articles: