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

//CharacterSet.cpp
#include "CharacterSet.h"

CharacterSet::CharacterSet()
	{
	inputSymbols=NULL;
	numOfSymbols=0;
	}
		
CharacterSet::CharacterSet(char *characters)
	{
	numOfSymbols=strlen(characters);
	inputSymbols=new char[numOfSymbols+1];
	strcpy(inputSymbols,characters);
	}
	
void CharacterSet::setInputSymbols(char *characters)
	{
	numOfSymbols=strlen(characters);
	inputSymbols=new char[numOfSymbols+1];
	strcpy(inputSymbols,characters);
	}

char CharacterSet::getSymbol(int i)
	{
	if(i>=numOfSymbols)
		{
		std::cout<<"requested symbol out of bound";
		return (-1);
		}
	return inputSymbols[i];
	}

int CharacterSet::getNumOfSymbols()
	{
	return numOfSymbols;
	}

//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;
		}
	}

#include "state.h"

STATE::STATE()
	{
	state=INTERMEDIATE;
	}
	
void STATE::setStateType(StateType type)
	{
	state=type;
	}

void STATE::setCharacterSet(CharacterSet &characters)
	{
	sigma=&(characters);
	}
	
void STATE::setTransitions(Transitions &tuple)
	{
	delta=&(tuple);
	}

StateType STATE::getStateType()
	{
	return state;
	}

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

DFA::DFA()
	{
	Q=NULL;
	currentState=NULL;
	}

void DFA::setDFA(STATE *setOfStates,int numberOfStates,STATE &initialState)
	{
	Q=setOfStates;
	numOfStates=numberOfStates;
	
	initialState.setStateType(INITIAL);
	
	currentState=&initialState;
	}
	
int DFA::processString(char *inputString)
	{
	/*
	These are the possible return values and there meaning:
	0.The string corresponds to a valid input for the DFA
	1.The string does not fit into the DFA
	2.Invalid symbol in input string
	*/
		//STATE curState=*currentState;
	for(int i=0;inputString[i]!='\0';i++)
		{
		if(!currentState->delta->getTransition(inputString[i],&currentState))
			return 2;
		}
	if(currentState->getStateType()==FINAL)
		return 0;
	else
		return 1;
	}

[flide]

Thank you ppl so very much, this forum was as much helpful as expected...

[Computergeek01]

First of all yuppie, no one knows WTF you're talking about. I had to google the term and now that I remember some obscure term like this from my freshmen year fo college I can tell you that this is done with what is called a "switch statement". I know the words aren't as big as you would hope to use in order to impress your family during this coming holiday season but programmers are more concerned with accomplishing things then looking smart. Here's your link yuppie: http://www.cplusplus.com/doc/tutorial/control/

EDIT: If you can condecend to visit this site again do be a good sport and mark this as solved.

[Computergeek01]

Reading more into this subject I can say that you can also do this with srand() since it really doesn't matter what your output will be as long as you set your limits the right way you have nothing to worry about.

It's psuedo-intellectual trolling like this that really gets under my skin, you read some article in some rag magazine about "Kwantum-Compooterin" and find a term with some big words and now you try to talk down to people while slapping together some crap code using words that remind us of boring hours in highschool math.

I'll leave the smallest possibility open that you might not be some punk kid that got trolled out of 4chan and you have a legitimate use for this but you haven't shown anything to prove it.

[flide]

I don't have to prove anything and as far as "switch statement" is concerned i could have used it if i wanted to implement just one particular DFA, but rather my aim was to develop a generic program that should be able to simulate any DFA...

and as i can see you are more interested in making the program run rather than making it do what it is meant to do, I don't think you have enough capability to even understand what is needed to do.

I am marking this thread as solved, not because you helped solve it, but because you want it so...

[rocketboy9000]

If you're still there, I have a suggestion: Use metaprogramming. Your program could write, and then run, a custom program for the N/DFA in question. In interpreted languages this is easy. In c++, I would say you should make a virtual machine, and write a program for it. Alternatively, if you dare, you could mmap some memory, write raw x86 opcodes in there, and then mmap it again (this time with exec privileges) and use inline assembly to jump into it. How's that?

[Computergeek01]

Not to bump a dead thread but the idea here is that once you observe the state of the system in question you have changed it. so what you want to return is a range that can be used to the possible state of the system without the need to interact with it, like that crazy guy with the radioactive grenade said?

http://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat

To over simplify it, in effect it's supposed to be away of calculating the possible outcome of something in a system without having to run through each and every equation needed to do so in the traditional sense. I wasn't just being a troll when I brought up Quantum Computers, this is the kind of task they are specifically being developed for.