Non Deterministic Finite Automata implementation

[flide]

Hello friends,

I designed few classes to simulate any DFA and it runs fine, now I want to do the same for a NDFA. The major problem that arises with it is the possibility of transiting to multiple states on a single input and epsilon-transitions.

for an overview i am posting here the .h files which essentially define the class structures for the DFA, and the main program for the simulation of a example DFA.
I think there need to be only very small modifications to get the code adapted for NDFA ( I think "Transitions" class needs the tweak ), but I am unable to find a way. Your help will be really appreciated.

//CharacterSet.h
#include <iostream>
#include <string.h>
#include <stdio.h>

#ifndef _CharacterSet_H
#define _CharacterSet_H

class CharacterSet
	{

private:
	char *inputSymbols;
	int numOfSymbols;

public:
	CharacterSet();
		
	CharacterSet(char *characters);
	
	void setInputSymbols(char *characters);
		
	char getSymbol(int i);
	
	int getNumOfSymbols();
		
	};

#endif

//state.h
#ifndef _STATE_H
#define _STATE_H

class STATE;

#ifndef __TRANSITIONS_H
#include "transitions.h"
#endif



enum StateType {INITIAL,INTERMEDIATE,FINAL};

class STATE
	{
public:

	StateType state; //defines type of state --> 0-initial, 1-intermediate or 2-final
	Transitions *delta;
	CharacterSet *sigma;

	STATE();
	
	void setStateType(StateType type);
	
	void setCharacterSet(CharacterSet &characters);
	
	void setTransitions(Transitions &tuple);
	
	StateType getStateType();
	
	};
	
#endif

//transitions.h
#include <stdarg.h>
#include "CharacterSet.h"

#ifndef _TRANSITIONS_H
#define _TRANSITIONS_H

class Transitions;

#ifndef _STATE_H
#include "state.h"
#endif


class Transitions
	{
	/*
	single object of class transition
	stores the transition of a single state on 
	every possible input symbol.
	*/
public:
	STATE *q; //whose transition is it
	CharacterSet *sigma; //what are the valid characters
	STATE **transitionPointers;

	Transitions();
	Transitions(STATE *stateX,CharacterSet &characters);
	void setInitials(STATE &stateX,CharacterSet &characters);
	void setTransitions(int count,...);		
	int getTransition(char input,STATE **next);	//returns 1 on successful assignment else 0
	};

#endif

//dfa.h
#include "CharacterSet.h"
#include "state.h"
#include "transitions.h"

class DFA
	{
	/*
	The class DFA should store only the possible states
	and each state in turn is responsible for showing next state.
	*/
private:
	STATE *Q;	//array of states of DFA, array can/will be dynamically allocated
	STATE *currentState;	//the current state of DFA
	int numOfStates;
public:
	DFA();
	void setDFA(STATE *setOfStates,int numberOfStates,STATE &initialState);
	int processString(char *inputString);
	};

//main.cpp
#include "dfa.h"

const int TOTAL_STATES=4;
char VALID_CHARACTER_SET[]="ab";

int main()
	{
	//Initial Definations
	DFA dfa;
	CharacterSet symbols(VALID_CHARACTER_SET);
	STATE q[TOTAL_STATES];
	Transitions table[4];
	
	//setting up the inter-relation among the components of DFA
	for(int i=0;i<TOTAL_STATES;i++)
		{
		q[i].setCharacterSet(symbols);
		q[i].setTransitions(table[i]);
		table[i].setInitials(q[i],symbols);
		}
	
	//setting up the transition table
	table[0].setTransitions(symbols.getNumOfSymbols(), &(q[1]) , &(q[0]) );
	table[1].setTransitions(symbols.getNumOfSymbols(), &(q[0]) , &(q[2]) );
	table[2].setTransitions(symbols.getNumOfSymbols(), &(q[3]) , &(q[1]) );
	table[3].setTransitions(symbols.getNumOfSymbols(), &(q[3]) , &(q[0]) );
	
	//setting up the final staes
	q[3].setStateType(FINAL);
	
	//setting up the DFA
	dfa.setDFA(q,TOTAL_STATES,q[0]);
	
	std::cout<<"\n\nDFA currently under question :\n";
	std::cout<<"			|	a		b	\n";
	std::cout<<"---------------------------------------------------\n";
	std::cout<<"	>q0		|	q1		q0	\n";
	std::cout<<"	 q1		|	q0		q2	\n";
	std::cout<<"	 q2		|	q3		q1	\n";
	std::cout<<"	*q3		|	q3		q0	\n";	
	
	//get the string
	std::cout<<"\n\n Enter the string to be checked : ";
	char inputString[20];
	std::cin>>inputString;
	
	//process the inputed string on the DFA
	int result=dfa.processString(inputString);
	switch(result)
		{
		case 0:
			std::cout<<"The string corresponds to a valid input for the DFA \n";
			break;
		case 1:
			std::cout<<"The string does not corresponds to a valid input for the DFA\n";		
			break;
		case 2:
			std::cout<<"Invalid symbol in input string\n";
		}
		
	}

and just for the curious ones

//transition.cpp
#include "transitions.h"

Transitions::Transitions()
	{
	q=NULL;
	sigma=NULL;
	transitionPointers=NULL;
	}

Transitions::Transitions(STATE *stateX,CharacterSet &characters)	
	{
	q=stateX;
	sigma=&(characters);
	transitionPointers=new STATE*[sigma->getNumOfSymbols()]; //Verified that this statement is valid and initializes a array of pointers
	}

void Transitions::setInitials(STATE &stateX,CharacterSet &characters)
	{	
	q = &(stateX);
	sigma=&(characters);
	transitionPointers=new STATE*[sigma->getNumOfSymbols()];
	}
	
void Transitions::setTransitions(int count,...)
	{
	unsigned int value;
	void *ptr;
	va_list arguments;
	va_start(arguments,count); 
	for(int i=0;i<count;i++)
		{
		value=(va_arg(arguments,unsigned int));
		ptr=(void *)value;
		transitionPointers[i]=static_cast<STATE*>(ptr);
		}
	va_end(arguments);
	}
	
int Transitions::getTransition(char input,STATE **next)	//returns 1 on successful assignment else 0
	{
	int location=-1;
	for(int i=0;i<(sigma->getNumOfSymbols());i++)
		{
		if(sigma->getSymbol(i)==input)
			{
			location=i;
			}
		}
	if(location==-1)
		{
		//std::cout<<"no transition found for given character";
		*next=NULL;
		return 0;
		}
	else
		{
		*next=transitionPointers[location];
		return 1;
		}
	}

I am thinking about structuring the new NDFA class in the following order

//ndfa.h
#include "CharacterSet.h"
#include "state.h"
#include "transitions.h"

struct CurrentStateList
	{
	STATE *present;
	STATE *next;
	};

class NDFA
	{
	/*
	The class NDFA should store only the possible states
	and each state in turn is responsible for showing next state.
	
	NDFA is different from DFA in respect that it can have multiple
	currentStates which will we created and destroyed dynamically.
	*/
private:
	STATE *error;	//state for undefined transitions.
	STATE *Q;	//array of states of DFA, array can/will be dynamically allocated
	CurrentStateList *currentState;	//the current states of NDFA
	int numOfStates;
	int numOfCurrentStates;
public:
	NDFA();
	void setNDFA(STATE *setOfStates,STATE &errorState, int numberOfStates, STATE &initialState);
	int processString(char *inputString);
	};
	
/*
Current problem for NDFA is the multiple transitions from a single state for a single symbol,
currently the Transitions class does not support it.
*/

I don't want anyone to waste his/her time coding the ndfa class, I just need the idea, the little tweak, that I am missing to create it myself.