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.

If you find any mistake above, kindly email to [email protected]

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

Related Posts:

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

Recommended Articles: