This assignment involves the construction of a NFA-to-DFA program. You are to wo
ID: 3729380 • Letter: T
Question
This assignment involves the construction of a NFA-to-DFA program. You are to work by yourself.
Given a NFA, M1 = (Qn, n , n, sn, Fn), write a program that will convert it to a DFA, M2 = (Qd, d,
d, sd, Fd). The states in Qn are zero-indexed integer values. This means 0 is a state, if |Qn| = 3, then Qn= {0, 1, 2}. The alphabet, n = d = , is restricted to lowercase letters.
The format for the input will consist of the following components, each on separate lines:
|Qn| The cardinality of Qn
In the form of a non-delimited string
|Fn| F1 F2 ... Fk The cardinality of Fn, followed by each of the accepting states, separated by
whitespace where k = |Fn|
sn The start state
Finally, n, the transition function, each on a line, given in 3-tuples, qi a qj. qi and qj are integer values, and a is a symbol in the alphabet, , with a space separating each.
The input example that follows is similar to Fig. 2.9 from the text on page 56:
3 ab
1 2
0
0 a 0
0 b 0
0 a 1
1 b 2
The format of the output mirrors the input. It will consist of the following components, each on separate lines:
|Qd| The cardinality of Qd
In the form of a non-delimited string
|Fd| F1 F2 ... Fk The cardinality of Fd, followed by each of the accepting states, separated by
whitespace where k = |Fd|
sd The start state
Finally, d, the transition function, each on a line, given in 3-tuples, qi a qj. qi and qj are integer values, and a is a symbol in the alphabet, , with a space separating each.
Output produced from example:
3 ab
1 2
0
0 a 1
0 b 0
1 a 1
1 b 2
2 a 1
2 b 0
Explanation / Answer
#include <cstdio>
#include <fstream>
#include <iostream>
#include <bitset>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
#define MAXIMUM_NFA_STATE 20
#define MAXIMUM_ALPHABET_SIZE 20
using namespace std;
class NFAstate
{
public:
int transitions[MAXIMUM_ALPHABET_SIZE][MAXIMUM_NFA_STATE];
NFAstate()
{
for (int i = 0; i < MAXIMUM_ALPHABET_SIZE; i++)
for (int j = 0; j < MAXIMUM_NFA_STATE; j++)
transitions[i][j] = -1;
}
}*NFAstates;
//DFA state representation
struct DFAstate
{
bool finalState;
bitset<MAXIMUM_NFA_STATE> constituentNFAstates;
bitset<MAXIMUM_NFA_STATE> transitions[MAXIMUM_ALPHABET_SIZE];
int symbolicTransitions[MAXIMUM_ALPHABET_SIZE];
};
set<int> NFA_finalState;
vector<int> DFA_finalStates;
vector<DFAstate*> DFAstates;
queue<int> incompleteDFAstates;
int N, M;
// N=No. of states
//M=Size of input alphabet
void ephsilonClosure(int state, bitset<MAXIMUM_NFA_STATE> &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;
ephsilonClosure(NFAstates[state].transitions[0][i], closure);
}
}
//finnd the ephsilon closure of staes and store it
void ephsilonClosure(bitset<MAXIMUM_NFA_STATE> state,
bitset<MAXIMUM_NFA_STATE> &closure)
{
for (int i = 0; i < N; i++)
if (state[i] == 1)
ephsilonClosure(i, closure);
}
// returns a bitset (the set of states the NFA could be in after moving from state X on input symbol A)
void NFAmovement(int x, int A, bitset<MAXIMUM_NFA_STATE> &y)
{
for (int i = 0; i < N && NFAstates[x].transitions[A][i] != -1; i++)
y[NFAstates[x].transitions[A][i]] = 1;
}
void NFAmovement(bitset<MAXIMUM_NFA_STATE> x, int a, bitset<MAXIMUM_NFA_STATE> &y)
{
for (int i = 0; i < N; i++)
if (x[i] == 1)
NFAmovement(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_finalState.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;
ephsilonClosure(0, DFAstates[0]->constituentNFAstates);
for (j = 0; j < N; j++)
if (DFAstates[0]->constituentNFAstates[j] == 1 && NFA_finalState.find(
j) != NFA_finalState.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++)
{
NFAmovement(DFAstates[x]->constituentNFAstates, i,
DFAstates[x]->transitions[i]);
ephsilonClosure(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_finalState.find(j) != NFA_finalState.end())
{
DFAstates[d]->finalState = true;
DFA_finalStates.push_back(d);
break;
}
incompleteDFAstates.push(d);
d++;
}
}
}
//write the DFA to a file
ofstream fout("DFA.txt");
fout << d << " " << M << " " << DFA_finalStates.size();
for (vector<int>::iterator it = DFA_finalStates.begin(); it
!= DFA_finalStates.end(); it++)
fout << " " << *it;
fout << " ";
for (i = 0; i < d; i++)
{
for (j = 1; j <= M; j++)
fout << i << " " << j << " "
<< DFAstates[i]->symbolicTransitions[j] << " ";
}
fout.close();
return 0;
}