NFA to DFA

[r]

hi there,
does anyone has any idea or a simple code that converts NFA to DFA.
NFA - Non deterministic finite automaton
DFA - Deterministic finite automaton

i would really apreciate any help i can get.

 

[Jonathan Turkanis]

hi there,
does anyone has any idea or a simple code that converts NFA to DFA.
NFA - Non deterministic finite automaton
DFA - Deterministic finite automaton

i would really apreciate any help i can get.

Looking at a proof that DFA's can simulate NFA's should tell you how
to convert an NFA to a DFA. Unfortunately the resulting DFA could be
extremely inefficient.

To produce a DFA which will be suitably efficient requires some
knowledge of your intended application.

Jonathan

 

[Donovan Rebbechi]

hi there,
does anyone has any idea or a simple code that converts NFA to DFA.
NFA - Non deterministic finite automaton
DFA - Deterministic finite automaton

i would really apreciate any help i can get.

If the set of states in the DFA is S, the set of states in the NFA is
the powerset 2^S (the set of subsets of S). The start state of the
NFA is the set of start sets of the DFA, and the transition maps
are induced by the transition map of the NFA, it's a map
f: 2^S x L -> 2^S where L is the set of symbols, so f({s1,s2,...,sn},a) =
the union of f'(s1,a), where f':SxL->2^S is the transition map for the NFA.
Or something like that.

As was mentioned, how you convert it depends on how you've coded it. Depending
on the number of states, it might not be a good idea to try to store all of
the states in memory, since you get the exponential blowup effect when you do
the conversion.

Cheers,

 

[red floyd]

hi there,
does anyone has any idea or a simple code that converts NFA to DFA.
NFA - Non deterministic finite automaton
DFA - Deterministic finite automaton

i would really apreciate any help i can get.

This is most likely a homework assignment. I did something similar many years
ago in my CS language theory class.

 

[Martijn Lievaart]

hi there,
does anyone has any idea or a simple code that converts NFA to DFA.
NFA - Non deterministic finite automaton
DFA - Deterministic finite automaton

In addition to what the others said, you may want to look at "the dragon
book" ("compilers, principals, techniques and tools" by Aho e.a.), it has
a lot on NFA/DFA conversion as it applies to compilers.

May be interesting to your problem, a good read anyhow.

HTH,
M4

 

[Ricky]

thanks for the reply sir,
i have coded the following so far, and i think i am stucked here. actually i
know what should i do, but can not succed to do it. please look at this code
and tell me if i can make the conversion from this structure, and iff
possible (dont wanna bother you) an optional solution from here.
thanks beforehand,

struct TLink
{
int linkNode;
int stringMax;
int string[5];
};

struct Node
{
int isFinalState;
int max_links;
TLink Link[5];
} NFA[5];

struct DLink
{
int meCilinLidhet;
int stringNo;
int node[5];
};

struct NodeD
{
int stringNode;
int isFinalState;
int max_links;
DLink Link[5];
} DFA[5];

int max_states;
int maxNode;

void NFA_input()
{
int i, j, k, f;
cout<<"\nHow MAny states does the NFA has =";
cin>>max_states;
for (i=0; i<max_states; i++)
{
cout<<"\nIs State q["<<i<<"] final State ? (yes=1, No=0)";
cin>>NFA.isFinalState;
cout<<"\nHow many transitions does this State have ?";
cin>>NFA.max_links;
for (j=0; j<NFA.max_links; j++)
{
cout<<"\nThe "<<j+1<<" transition is linking state q["<<i<<"] with
state =";
cin>>NFA.Link[j].linkNode;
cout<<"\nHow many strings make this transition=";
cin>>NFA.Link[j].stringMax;
for (k = 0; k < NFA.Link[j].stringMax; k++)
{
cout<<"\nEnter those strings=\n";
cout<<"delta["<<k+1<<"]= ";
cin>>NFA.Link[j].string[k];
}
}
}
}

void print_NFA()
{
int i, j, k ;
for (i=0; i<max_states; i++)
{
cout<<"\nState q["<<i<<"]";
for (j=0; j<NFA.max_links; j++)
{
cout<<"\n is linked with state q["<<NFA.Link[j].linkNode<<"]";
cout<<" with string";
for (k = 0; k < NFA.Link[j].stringMax; k++)
cout<<" " <<NFA.Link[j].string[k];
}
cout<<"\n";

}
cout<<"\nInitial State of the automata is:q[0]\n ";
cout<<"\nFinal States of the automata are: ";
for (i=0; i<max_states; i++)
{
if (NFA.isFinalState == 1)
cout<<"\n q["<<i<<"] \t";
}
}
int main()
{
clrscr();
char line[80]="-------------------------------------------------";
NFA_input();
cout<<"\nTranitions of the NFA are: \n";
cout<<line;
print_NFA();
cout<<"\n"<<line;
cin.get(); cin.ignore();
return 0;
}

 

[Donovan Rebbechi]

thanks for the reply sir,
i have coded the following so far, and i think i am stucked here. actually i
know what should i do, but can not succed to do it. please look at this code
and tell me if i can make the conversion from this structure, and iff
possible (dont wanna bother you) an optional solution from here.
thanks beforehand,

I don't understand why you're using such primitive data structures to represent
what looks like some kind of graph based automaton. Shouldn't the nodes be
dynamically allocated ?

For example, here's how I'd start with a DFA (NFA is similar)

typedef char Symbol_t; // the symbols in our regular language
typedef std::vector<Symbol_t> Word_t;
typedef std::map<Symbol_t, State*> transition_t;

struct State
{
// for each Symbol, we have a transition from this node
// to another node.
std::map<Symbol_t , State*> transition;

// for convenience: each state should probably have a label.
std::string id;
};

// declare the interface
class DFA
{
virtual bool accepted (const std::vector<Symbol_t>& v) = 0;
};

class GraphDFA
{
std::list<State> states;
State* s0; // initial state
std::vector<State*> acceptStates;
public:
// test to see if a word is accepted. This code might be wrong, and probably is ...
bool accepted ( const std::vector<Symbol_t>& v )
{

State* s = s0;
transition_t::const_iterator j;
for (Word_t::const_iterator it
= v.begin(); it!=v.end(); ++it )
{
j = s->transition.find(*it);
// no transition defined: implicit fail state transition.
if (j == s->end())
return false;
else
s = j->second;
}
// done reading the word
return (std::find ( acceptStates.begin(),acceptStates.end(), s )!=acceptStates.end());
}
};

As I said, there are two ways that you could proceed with the NFA -> DFA conversion.

One would be to try to convert the graphs. This would require constructing one vertex for
each subset of the states of the NFA. The simplest way to do that would be to have 1 bit
representing each state, and then you have a binary number representing each state (look up
the proof that the size of the powerset is 2^N if you don't understand this). Then you'd
need to create a graph for each one.

A simpler way would be to re-implement the interface by subclassing. You'd still need a
data structure that could hold sets of states, for example s1 of type
std::set<State*> because the current state in your new DFA is a list of NFA
states. You compute a new set<State*> s2 from this by following all the
transition arrows from each state in the set s1, and appending the endpoints of those
transitions to s2. That at least enables you to test whether or not a word is accepted.

If you want some verbose printout of the graph structure, you can still do that without
constructing the graph. What you'd need to do is iterate over all states (all possible
set<State*> s with each element in your alphabet) and compute the transition arrows
from each (in same manner as in accept method) and find a way to describe the states.

HTH,