************************************************** **/
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<string.h>
#include<iomanip.h>
#define MAX_STATES 500
#define MAX_INPUTS 50
/************************************************** *********************************/
/* I have used Linked Lists to dynamically allocate the states */
/* I found Linked lists are very useful as after transormation states */
/* may be more than one.I have written functions in LinkedList class */
/* and their function easily known by seeing their name */
/* GetAllInfo function returns the length of the LinkedList and copies*/
/* all elements into an Array.I used Templates to input the states */
/* and Input symbols.I prefered to input integers as input symbols */
/* as with integers we can make the program more easier */
/* I overloaded '<<' operator to output the states as q followed by */
/* the number of that particular state. */
// NODE STRUCTURE OF LINKED LIST NODE
template<class T>
struct LinkedListNodeType
{
LinkedListNodeType<T> *Next;
T NodeInfo;
LinkedListNodeType<T> *Prev;
};
/////////////////////////////////////////////////////////////////////////////////////
// LINKED LIST CLASS HEADER SECTION
template<class T>
class LinkedList
{
// OVERLOADING << OPERATOR TO OUT PUT THE LINKED LIST
friend ostream& operator<<(ostream& os,const LinkedList<T> &temp)
{
LinkedListNodeType<T> *curr = temp.Head->Next;
// WE WILL TRAVERSE UNTIL HEAD
while (curr != temp.Head)
{
os<<" q"<<curr->NodeInfo;
curr = curr->Next;
}
return os;
}
private:
LinkedListNodeType<T> *Head;
public:
LinkedList();
void Find( T NodeInfo,bool& found,LinkedListNodeType<T>* &curr );
void Insert(T NodeInfo);
bool IsEmpty();
T RemoveFirst();
void GetAllInfo(T Array[1000],int &Length);
};
//////////////// LINKED LIST IMPLEMENTATION SECTION ////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////
// DEFAULT CONSTRUCTOR WITH NO ARUGUMENTS
template<class T>
LinkedList<T>::LinkedList()
{
// INITIALIZING HEADER [DUMMY NODE]
Head=new LinkedListNodeType<T>;
Head->Next=Head;
Head->Prev=Head;
}
/////////////////////////////////////////////////////////////////////////////////////
// TO FIND AN ELEMENT IN THE LIST IF IT IS NOT THERE RETURN THE APPROPRIATE INSERETING POSITION
template<class T>
void LinkedList<T>:: Find( T NodeInfo,bool& found,LinkedListNodeType<T>* &curr )
{
curr = Head->Next;
// TRAVERSE UNTIL HEAD OR NODE LESS THE CURRENT NODE
while ((curr != Head)&&(curr->NodeInfo < NodeInfo))
curr = curr->Next;
// Set FOUND. If list is empty or value is not located, then found will
// return FALSE. TRUE is only returned if the value is located.
if( curr == Head )
found = false;
else
found = (curr->NodeInfo == NodeInfo);
}
/////////////////////////////////////////////////////////////////////////////////////
// TO INSERT AN ELEMENT IN TO LINKED LIST
template<class T>
void LinkedList<T>::Insert(T NodeInfo)
{
bool found;
LinkedListNodeType<T> *p,*noo,*n;// P : PREV NODE; NOO : NEW NODE; N : NEXT NODE
// SET N
Find(NodeInfo,found, n );
// SET P AND ALLOCATE A NEW NODE SETTING C TO POINT TO IT
p = n->Prev;
noo = new LinkedListNodeType<T>;
// ADJUST POINTERS IN 'NOO' TO POINT TO 'P' AND 'N'. ALSO PUT VALUE IN NODE
noo->Prev = p;
noo->NodeInfo = NodeInfo;
noo->Next = n;
// ADJUST POINTER IN PREVIOUS AND NEXT NODES TO POINT TO NEW NODE
p->Next = noo;
n->Prev = noo;
}
/////////////////////////////////////////////////////////////////////////////////////
// TO TEST WHETHER THE LIST IS EMPTY OR NOT
template<class T>
bool LinkedList<T>::IsEmpty()
{
LinkedListNodeType<T> *curr = Head->Next;
int count=0;// USING COUNT PARAMETER TO COUNT NUMBER OF ELEMENTS IN THE LIST
while (curr != Head)
{
count++;
curr = curr->Next;
}
//TESTING COUNT
if(count>0)
return false;
else
return true;
}
/////////////////////////////////////////////////////////////////////////////////////
// TO REMOVE FIRST ELEMENT FROM THE LIST
template<class T>
T LinkedList<T>::RemoveFirst()
{
T ReturningInfo;// RETURNING NODE
LinkedListNodeType<T> *curr = Head->Next;
ReturningInfo = curr->NodeInfo;
// REARRANGING THE POINTERS TO POINT TO NEXT NODE OF CURRENT NODE
curr->Next->Prev=Head;
Head->Next=curr->Next;
delete curr;// RELEASING THE MEMORY
return ReturningInfo;
}
/////////////////////////////////////////////////////////////////////////////////////
// TO RETURN ALL NODE ELEMENTS IN A ARRAY WHICH ARE COPIED FROM LINKEDLIST
template<class T>
void LinkedList<T>::GetAllInfo(T Array[1000],int &Length)
{
Length=0;
LinkedListNodeType<T> *curr = Head->Next;
// TRAVERSING ALL NODES AND COPYING ELEMENTS INTO ARRAY
while (curr != Head)
{
Array[Length]=curr->NodeInfo;
Length++;
curr = curr->Next;
}
}
/************************************************** *********************************/
///////////////////////// CLASS SET HEADER SECTION //////////////////////////////////
/* I have Used Set class to represent all states as sets and these sets will use */
/* all of the LinkedList functions .These Sets are important particularly whenever */
/* combining one or more states into a single state.This function will reduce the */
/* redundancy and returns s set which is a union of all the given sets. All */
/* function name itself specifies what they do. I have overloaded '=' , '==' and */
/* '<<' operators.'=' assigns one set to another set ,'==' returns true if two sets*/
/* are equal and returns false if they are not equal. '<<' operator will gives the */
/* output in closed round braces .If there isno state it will return Null with braces*/
/* Each of the function used in Set class inturn */
/* uses one or more functions of the LinkedLlist */
template<class T>
class Set
{
// OVERLOADING OPERATOR << TO OUTPUT THE SET
friend ostream& operator<<(ostream& os,const Set<T> &temp)
{
if(temp.NumberOfElements)
os<<"("<<temp.ElementsList<<")";
else
os<<"(NULL)";
return os;
}
private:
int NumberOfElements;// TO COUNT THE NUMBER OF ELEMENTS OF THE SET
LinkedList<T> ElementsList;// TO STORE THE ELEMENTS OF THE SET
public:
Set();
void Insert(T Element);
T Remove();
bool IsElementPresent(T Element);
bool IsEmpty();
void GetAllInfo(T Array[1000],int &Length);
Set& Union(Set A,Set B);
Set& operator=(Set A);
bool operator==(Set A);
void SetToNull();
};
//////////////////////// IMPLEMENTATION SECTION OF SET /////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////
// DEFAULT CONSTRUCTOR FOR SET CLASS
template<class T>
Set<T>::Set()
{
NumberOfElements=0;
}
/////////////////////////////////////////////////////////////////////////////////////
/// INSERING A ELEMENT INTO SET
template<class T>
void Set<T>::Insert(T Element)
{
if(!IsElementPresent(Element))
{
NumberOfElements++;// INCREASING THE COUNT OF SET
ElementsList.Insert(Element);// INSERTING INTO LINKEDLIST
}
}
/////////////////////////////////////////////////////////////////////////////////////
// REMOVING LEAST COST ELEMENT FROM SET
template<class T>
T Set<T>::Remove()
{
NumberOfElements--;// DECREMENTING COUNT OF SET
return ElementsList.RemoveFirst(); // CALLING REMOVE FUNCTION OF LINKEDLIST
}
/////////////////////////////////////////////////////////////////////////////////////
// TO CHECK WHETHER THE SET IS EMPTY OR NOT
template<class T>
bool Set<T>::IsEmpty()
{
//CALLING THE EMPTY MEMBER FUNCTION OF LINKED LIST
return ElementsList.IsEmpty();
}
/////////////////////////////////////////////////////////////////////////////////////
// TO SEARCH A ELEMENT IN THE SET
template<class T>
bool Set<T>::IsElementPresent(T Element)
{
bool found;
LinkedListNodeType<T>* curr;
// CALLING FIND MEMBER FUNCTION OF LINKED LIST
ElementsList.Find(Element,found,curr);
return found;
}
/////////////////////////////////////////////////////////////////////////////////////
// TO GET ALL INFO OF SET INTO AN ARRAY
template<class T>
void Set<T>::GetAllInfo(T Array[1000],int &Length)
{
// CALLING GETALLINFO MEMBER FUNCTION OF LINKED LIST
ElementsList.GetAllInfo(Array,Length);
}
/////////////////////////////////////////////////////////////////////////////////////
// COMBINING TWO SET BY UNION OPERATION
template<class T>
Set<T>& Set<T>::Union(Set A,Set B)
{
T Array[1000];
int Length,i;
// ALL INFORMATION OF SET A INTO ARRAY AND INSERTING INTO NEW SET
A.GetAllInfo(Array,Length);
for(i=0;i<Length;i++)
Insert(Array[i]);
B.GetAllInfo(Array,Length);
// ALL INFORMATION OF SET B INTO ARRAY AND BY NOT INSERTING FOUND ELEMENTS IN THE SET
for(i=0;i<Length;i++)
{
if(!IsElementPresent(Array[i]))
Insert(Array[i]);
}
return *this;
}
/////////////////////////////////////////////////////////////////////////////////////
// OVERLOADING = OPERATOR FOR ASSIGNMNET
template<class T>
Set<T>& Set<T>::operator =(Set A)
{
T Array[1000];
int Length,i;
// ALL INFORMATION OF SET A INTO ARRAY AND INSERTING INTO NEW SET
A.GetAllInfo(Array,Length);
SetToNull();
for(i=0;i<Length;i++)
Insert(Array[i]);
return *this;
}
/////////////////////////////////////////////////////////////////////////////////////
// OVERLOADING == OPERATOR TO FIND EQUALITY
template<class T>
bool Set<T>::operator==(Set A)
{
T Array[1000],Array1[1000];
int Length,Length1,i;
bool flag=true;
GetAllInfo(Array,Length);
// ALL INFORMATION OF SET A INTO ARRAY AND INSERTING INTO NEW SET
A.GetAllInfo(Array1,Length1);
if(Length==Length1)
{
for(i=0;i<Length;i++)
{
if(Array[i]!=Array1[i])
flag=false;
}
return flag;
}
else
return false;
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
void Set<T>::SetToNull()
{
// CALLING REMOVE MEMBER FUNCTION OF LINKED LIST UNTIL LINKED LIST IS EMPTY
while(!IsEmpty())
Remove();
}
/////////////////////////////////////////////////////////////////////////////////////
/************************************************** *********************************/
int GetNumberOfState(Set<int> ALLStates[MAX_STATES],Set<int> temp,int Length)
{
for(int i=0;i<Length;i++)
if(ALLStates[i]==temp)
return i;
return -1;
}
/************************************************** *********************************/
int main()
{
Set<int> INFA[MAX_STATES][MAX_INPUTS],NFA[MAX_STATES][MAX_INPUTS],DFA[MAX_STATES][MAX_INPUTS],MinDFA[MAX_STATES][MAX_INPUTS],MDFAStates[MAX_STATES],ALLStates[MAX_STATES],LambdaT[MAX_STATES],temp,temp1,MinTemp,Mark[2*MAX_STATES],UnMark[2*MAX_STATES];
int i,j,k,MarkCount=0,UnMarkCount=0,States,NoInputs,Te mp,NextState,DFAstates,Array[MAX_STATES],Length,Length1,lambda,Input,NoFinalStates,Final[MAX_STATES],MDFAStatesNo[MAX_STATES];
bool flag,InputStates[MAX_STATES],FinalStates[MAX_STATES],MinDFAInputStates[MAX_STATES],MinDFAFinalStates[MAX_STATES];;
cout<<"Enter Number of states : ";
cin>>States;
cout<<"Enter Number of Inputs(without counting lambda) : ";
cin>>NoInputs;
cout<<"If there is Lambda transactions[1 for true,0 for false] :";
cin>>lambda;
for(i=0;i<States;i++)
{
if(lambda==1)
{
cout<<"Enter the No of Transitions for State "<<i<<" With Lambda "<<" :";
cin>>Temp;
for(k=0;k<Temp;k++)
{
cout<<"Enter transformed State "<<k+1<<" for state "<<i<<" with Lamdba "<<" :";
cin>>NextState;
LambdaT[i].Insert(NextState);
}
}
for(j=0;j<NoInputs;j++)
{
cout<<"Enter the No of Transitions for State "<<i<<" With Input "<<j<<" :";
cin>>Temp;
for(k=0;k<Temp;k++)
{
cout<<"Enter transformed state "<<k+1<<" for state "<<i<<" with input "<<j<<" :";
cin>>NextState;
INFA[i][j].Insert(NextState);
}
/**** input on both NFA,INFA ******************/
NFA[i][j]=INFA[i][j];
}
}
cout<<"Enter the Input State Number :";
cin>>Input;
cout<<"Enter the No of Final States :";
cin>>NoFinalStates;
for(k=0;k<NoFinalStates;k++)
{
cout<<"Enter "<<k+1<<" Final state :";
cin>>Final[k];
}
DFAstates=States;
cout<<endl<<"Here first state(first column) represents a state"
<<endl<<"After lambda transition and from 2nd to last"
<<endl<<"column represents a state after input symbols"
<<endl<<"from '0' to 'numberofinputsymbols-1' and "
<<endl<<"each of the row represents transformations"
<<endl<<"for state start from '0' to 'numberofstates-1' "<<"\n";
cout<<"Input NFA is as follows:"<<endl;
for(i=0;i<States;i++)
{
cout<<LambdaT[i];
for(j=0;j<NoInputs;j++)
{
cout<<setw(-20)<<INFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for prompt";cin>>c;}
if(lambda==1)
{
for(i=0;i<States;i++)
{
temp.SetToNull();
temp=LambdaT[i];
temp.Insert(i);
do{
temp.GetAllInfo(Array,Length);
for(k=0;k<Length;k++)
temp.Union(temp,LambdaT[Array[k]]);
temp.GetAllInfo(Array,Length1);
if((Length1-Length)==0)
break;
}while(1);
for(j=0;j<NoInputs;j++)
{
temp.GetAllInfo(Array,Length);
temp1.SetToNull();
//cout<<endl<<"for seacching After Lamba"<<endl<<temp<<endl;{char c;cin>>c;}
for(k=0;k<Length;k++)
{
if(!(INFA[Array[k]][j].IsEmpty()))
temp1.Union(temp1,INFA[Array[k]][j]);
//cout<<endl<<"After Inputsymbols "<<k<<"*"<<j<<"*"<<INFA[Array[k]][j]<<endl<<temp1<<endl;
}
do{
temp1.GetAllInfo(Array,Length);
for(k=0;k<Length;k++)
temp1.Union(temp1,LambdaT[Array[k]]);
temp1.GetAllInfo(Array,Length1);
//cout<<endl<<"After lamda trns"<<endl<<temp1<<endl;{char c;cin>>c;}
if((Length1-Length)==0)
break;
}while(1);
DFA[i][j]=temp1;
NFA[i][j]=temp1;
//cout<<endl<<"Fianllay"<<endl<<temp1<<endl;{char c;cin>>c;}
}
}
}
else
{
for(i=0;i<States;i++)
{
for(j=0;j<NoInputs;j++)
{
DFA[i][j]=NFA[i][j];
}
cout<<endl;
}
}
cout<<"*************** AFter removing lambda transitions *******************"<<endl;
cout<<"first row represents transformations for state 0 and latter rows"
<<endl<<"represents states incresing by '1'. Columns represents"
<<endl<<"transformations for each of the input symbol from 0 to"
<<endl<<"numberofinputsymbols-1 .Lambda transformations are removed"
<<endl;
for(i=0;i<States;i++)
{
for(j=0;j<NoInputs;j++)
{
cout<<setw(-20)<<NFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for prompt";cin>>c;}
/*** After removing lambda transitions ......Now converting into DFA *******/
/************************************************** **************************/
ALLStates[0].Insert(0);
temp.SetToNull();
DFAstates=1;//States;
do{
for(i=0;i<DFAstates;i++)
{
for(j=0;j<NoInputs;j++)
{
flag=false;
for(k=0;k<DFAstates;k++)
{
if(DFA[i][j]==ALLStates[k])
flag=true;
}
if(flag==false)
{
//cout<<"Found "<<DFA[i][j]<<endl;char c;cin>>c;
break;
}
}
if(flag==false)
break;
}
if(flag==false)
{
ALLStates[DFAstates]=DFA[i][j];
DFA[i][j].GetAllInfo(Array,Length);
for(i=0;i<NoInputs;i++)
{
temp.SetToNull();
for(j=0;j<Length;j++)
{
temp.Union(temp,NFA[Array[j]][i]);
//cout<<endl<<"After union with"<<Array[j]<<"*"<<i<<endl<<temp<<endl;{char c;cin>>c;}
}
//cout<<endl<<"Finally"<<DFAstates<<"*"<<i<<"*"<<tem p<<endl<<temp<<endl;{char c;cin>>c;}
DFA[DFAstates][i]=temp;
}
DFAstates++;
}
else
{
break;
}
}while(1);
cout<<endl<<"************* AFTER CONVERTING NFA TO DFA *********************"<<endl;
for(i=0;i<DFAstates;i++)
{
cout<<"For "<<ALLStates[i]<<" States are :";
for(j=0;j<NoInputs;j++)
{
cout<<setw(-15)<<DFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for prompt";cin>>c;}
cout<<endl<<"************* AFTER changing table *********************"<<endl;
cout<<endl<<"Rearranging the states which may contain more than one state"
<<endl<<"and renaming them with a single state.This naming will "
<<endl<<"from state '0' to increasing order of state:"<<endl;
cout<<endl<<"REARRANGED DFA IS AS FOLLOWS:"<<endl;
for(i=0;i<DFAstates;i++)
{
cout<<"For q"<<i<<" States are :";
for(j=0;j<NoInputs;j++)
{
Temp=GetNumberOfState(ALLStates,DFA[i][j],DFAstates);
DFA[i][j].SetToNull();
DFA[i][j].Insert(Temp);
cout<<setw(-15)<<DFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for prompt:";cin>>c;}
/* finding Starting and Final states */
for(i=0;i<DFAstates;i++)
{
InputStates[i]=ALLStates[i].IsElementPresent(Input);
FinalStates[i]=false;
for(j=0;j<NoFinalStates;j++)
{
if(ALLStates[i].IsElementPresent(Final[j]))
FinalStates[i]=true;
}
//cout<<"State q"<<i<<" Is "<<InputStates[i]<<"*"<<FinalStates[i]<<endl;
}
cout<<"starting States of DFA are: ";
for(i=0;i<DFAstates;i++)
{
if(InputStates[i]==true)
cout<<" q"<<i;
}
cout<<endl;
cout<<"Final States of DFA are: ";
for(i=0;i<DFAstates;i++)
{
if(FinalStates[i]==true)
cout<<" q"<<i;
}
cout<<endl;
{char c;cout<<"Input char for Prompt:";cin>>c;}
/**************** minimization of a Dfa ***************/
//MarkCount = 0;UnMarkCount = 0;
for(i=0;i<DFAstates-1;i++)
{
for(j=i+1;j<DFAstates;j++)
{
if( ((FinalStates[i]==true)&&(FinalStates[j]==false)) || ((FinalStates[i]==false)&&(FinalStates[j]==true)) )
{
Mark[MarkCount].Insert(i);
Mark[MarkCount].Insert(j);
MarkCount++;
}
else
{
if(i != j)
{
UnMark[UnMarkCount].Insert(i);
UnMark[UnMarkCount].Insert(j);
UnMarkCount++;
}
}
}
}
/*cout<<endl<<"Marked are";
for(i=0;i<MarkCount;i++)
cout<<endl<<Mark[i];
cout<<endl<<"un marked are";
for(i=0;i<UnMarkCount;i++)
cout<<endl<<UnMark[i];
*/
for(i=0;i<UnMarkCount;i++)
{
//cout<<"Unmarked now is"<<UnMark[i]<<endl;
UnMark[i].GetAllInfo(Array,Length);
for(j=0;j<NoInputs;j++)
{
MinTemp.SetToNull();
MinTemp.Union(DFA[Array[0]][j],DFA[Array[1]][j]);
for(k=0;k<MarkCount;k++)
{
if(MinTemp == Mark[k] )
{
//cout<<endl<<"Finally"<<DFAstates<<"*"<<i<<"*"<<tem p<<endl<<temp<<endl;{char c;cin>>c;}
Mark[MarkCount]=UnMark[i];
MarkCount++;
UnMark[i].SetToNull();
j=NoInputs;
break;
}
}
}
}
cout<<endl<<"After Marker algorithm "<<endl;
/*cout<<endl<<"marked are";
for(i=0;i<MarkCount;i++)
{
cout<<endl<<Mark[i];
}
cout<<endl<<"un marked are";
for(i=0;i<UnMarkCount;i++)
{
if(!UnMark[i].IsEmpty())
{
cout<<endl<<UnMark[i];
}
}
*/
/************** reduce algorithm *******************************/
/* Using mark procedure to find all pairs of Indistinguishable states */
for(i=0;i<UnMarkCount-1;i++)
{
if(!UnMark[i].IsEmpty())
for(j=0;j<UnMarkCount;j++)
{
if(!UnMark[j].IsEmpty())
{
UnMark[i].GetAllInfo(Array,Length);
for(k=0;k<Length;k++)
if(UnMark[j].IsElementPresent(Array[k])==true)
break;
if(UnMark[i].IsElementPresent(Array[k])==true)
{
temp.SetToNull();
temp.Union(UnMark[i],UnMark[j]);
UnMark[j].SetToNull();
UnMark[i]=temp;
}
}
}
}
/* Finding Sets of Indistinguishable states that are Not Marked */
cout<<endl<<"Finally ,After Merging UnMarked ...."
<<endl<<"i.e. finding distinguishable states:"<<endl;
cout<<endl<<"sets of distinguishable states which may contain more"
<<endl<<"more than one indistinguishable state:"<<endl;
for(i=0;i<UnMarkCount;i++)
{
if(!UnMark[i].IsEmpty())
{
cout<<endl<<UnMark[i];
}
}
for(i=0;i<DFAstates;i++)
{
ALLStates[i].SetToNull();
ALLStates[i].Insert(i);
ALLStates[i].GetAllInfo(Array,Length);
for(k=0;k<UnMarkCount;k++)
{
if(!UnMark[k].IsEmpty())
{
if(UnMark[k].IsElementPresent(Array[0])==true)
break;
}
}
if(UnMark[k].IsElementPresent(Array[0])==true)
ALLStates[i]=UnMark[k];
}
cout<<endl<<"Minimized DFA transformations are as follows:"<<endl;
cout<<endl<<"After rearranging the minimized DFA i.e. changing "
<<endl<<" a state which may contain more than one state "
<<endl<<"into a single state by numbering each of the "
<<endl<<" state in increasing order :"<<endl;
for(i=0;i<DFAstates;i++)
{
cout<<"For state "<<ALLStates[i]<<" Trans are:";
for(j=0;j<NoInputs;j++)
{
DFA[i][j].GetAllInfo(Array,Length);
for(k=0;k<UnMarkCount;k++)
{
if(!UnMark[k].IsEmpty())
{
if(UnMark[k].IsElementPresent(Array[0])==true)
break;
}
}
if(UnMark[k].IsElementPresent(Array[0])==true)
DFA[i][j]=UnMark[k];
cout<<DFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for Prompt:";cin>>c;}
cout<<endl<<"Minimized DFA States are as follows:"<<endl;
k=DFAstates;
DFAstates=0;
cout<<endl<<"After 'Reduce' algorithm some states have same name :"
<<endl<<"after removing these redundancy we get following"
<<endl<<"states:"<<endl;
/* GETTING MDFA STATES */
cout<<"The MDFA states are :"<<endl;
for(i=0;i<k;i++)
{
flag=false;
for(j=0;j<DFAstates;j++)
{
if(MDFAStates[j]==ALLStates[i])
flag=true;
}
if(flag==false)
{
MDFAStates[DFAstates]=ALLStates[i];
cout<<MDFAStates[DFAstates]<<endl;
MDFAStatesNo[DFAstates++]=i;
}
}
{char c;cout<<"Input char for Prompr:";cin>>c;}
/* COPYING MINDFA FROM DFA */
cout<<"After removing redundency minimized DFA is"<<endl;
Temp=0;
for(i=0;i<k;i++)
{
flag=false;
for(j=0;j<DFAstates;j++)
if(MDFAStatesNo[j]==i)
flag=true;
if(flag==true)
{
for(j=0;j<NoInputs;j++)
{
MinDFA[Temp][j]=DFA[i][j];
cout<<MinDFA[Temp][j];
}
Temp++;
cout<<endl;
}
}
{char c;cout<<"Input char for Prompt:";cin>>c;}
cout<<"After reordering numbers of states"<<endl;
cout<<"some states may contain more than one state"
<<endl<<"making those states number into one state number:"<<endl;
cout<<endl<<"Final minimized DFA is :"<<endl;
for(i=0;i<DFAstates;i++)
{
cout<<"For q"<<i<<" States are :";
for(j=0;j<NoInputs;j++)
{
Temp=GetNumberOfState(MDFAStates,MinDFA[i][j],DFAstates);
MinDFA[i][j].SetToNull();
MinDFA[i][j].Insert(Temp);
cout<<setw(-15)<<MinDFA[i][j];
}
cout<<endl;
}
{char c;cout<<"Input char for Prompt:";cin>>c;}
for(i=0;i<DFAstates;i++)
{
flag=false;
MDFAStates[i].GetAllInfo(Array,Length);
for(j=0;j<Length;j++)
{
if(InputStates[Array[j]]==true)
{
flag=true;
break;
}
}
MinDFAInputStates[i]=flag;
flag=false;
for(j=0;j<Length;j++)
{
if(FinalStates[Array[j]]==true)
{
flag=true;
break;
}
}
MinDFAFinalStates[i]=flag;
}
cout<<"starting States of minimized DFA are: ";
for(i=0;i<DFAstates;i++)
{
if(MinDFAInputStates[i]==true)
cout<<" q"<<i;
}
cout<<endl;
cout<<"Final States of minimized DFA are: ";
for(i=0;i<DFAstates;i++)
{
if(MinDFAFinalStates[i]==true)
cout<<" q"<<i;
}
cout<<endl;
{char c;cout<<"Input char for Prompt:";cin>>c;}
return 0;
}
/************************************ END OF PROGRAM *************************************/
