finite state automata

[ponaka_aruna]

how to implement deterministic finite state automata?

[mehdi62b]

using System;
using System.Collections;
namespace WindowsApplication1
{
/// <summary>
/// Summary description for DFA.
/// </summary>
///
interface IState
{
string Name {get;}
bool IsFinal{get;}
}
public class State:IState
{
string m_name=string.Empty;
bool m_isFinal=false;
public State(string name,bool isFinal)
{
m_name=name;
m_isFinal=isFinal;
}
public State(string name)
{
m_name=name;
m_isFinal=false;
}
public string Name
{
get
{
return m_name;
}
}
public bool IsFinal
{
get
{
return m_isFinal;
}
}
}
interface ITransitionFunction
{
State InputState{get;set;}
State OutputState{get;set;}
char InputSymbol{get;set;}
}
public class TransitionFunction:ITransitionFunction
{
State m_inputstate=null;
State m_outputstate=null;
char m_inputsymbol=char.MinValue;
public TransitionFunction(State inputstate,State outputstate,char inputsymbol)
{
m_inputstate=inputstate;
m_outputstate=outputstate;
m_inputsymbol=inputsymbol;
}
public State InputState
{
get
{
return m_inputstate;
}
set
{
m_inputstate=value;
}
}
public State OutputState
{
get
{
return m_outputstate;
}
set
{
m_outputstate=value;
}
}
public char InputSymbol
{
get
{
return m_inputsymbol;
}
set
{
m_inputsymbol=value;
}
}
}
interface IDFA
{
IList States{get;set;}
IList Symbols{get;set;}
State StartState{get;set;}
IList FinalStates{get;set;}
IList TransitionFunctions{get;set;}
}
public class DFA:IDFA
{
IList m_states=null;
IList m_symbols=null;
State m_start_state=null;
IList m_final_states=null;
IList m_transition_functions=null;
public DFA(IList states,IList symbols,State startstate,IList finalstates,
IList transitionfunctions)
{
m_states=states;
m_symbols=symbols;
m_start_state=startstate;
m_final_states=finalstates;
m_transition_functions=transitionfunctions;
IsDFA(this);
}
public DFA(IList states,IList symbols,State startstate,State finalstate,
IList transitionfunctions)
{
m_states=states;
m_symbols=symbols;
m_start_state=startstate;
m_final_states=new ArrayList();
m_final_states.Add(finalstate);
m_transition_functions=transitionfunctions;
IsDFA(this);
}
public IList States
{
get
{
return m_states;
}
set
{
m_states=value;
}
}
public IList Symbols
{
get
{
return m_symbols;
}
set
{
m_symbols=value;
}
}
public State StartState
{
get
{
return m_start_state;
}
set
{
m_start_state=value;
}
}
public IList FinalStates
{
get
{
return m_final_states;
}
set
{
m_final_states=value;
}
}
public IList TransitionFunctions
{
get
{
return m_transition_functions;
}
set
{
m_transition_functions=value;
}
}
private static void IsDFA(DFA DFA1)
{
ArrayList ar=new ArrayList();//to be used for earasing duplicated entries
//check for valid symbols
foreach(object o in DFA1.m_symbols)
{
if(!(o is char))
throw new Exception
("one of your input symbols is not in the correct format");
char ch=(char)o;
if(!ar.Contains(ch))
ar.Add(ch);
}
DFA1.m_symbols=(IList)ar.Clone();
//check for valid states
ar.Clear();
foreach(object o in DFA1.m_states)
{
if(!(o is State))
throw new Exception
("one of your states is not in the correct format");
State st=o as State;
if(!ar.Contains(st))
ar.Add(st);
}
DFA1.m_states=(IList)ar.Clone();
//check for valid final states
foreach(object o in DFA1.m_final_states)
if(!DFA1.m_states.Contains(o))
throw new Exception
("one of your final states doesn't exist in your states");
//check transition functions for duplicated
ar.Clear();

foreach(object o in DFA1.m_transition_functions)
{
if (!(o is ITransitionFunction))
{
throw new Exception
("one of your functions is not in the correct format");
}
ITransitionFunction Itf=o as ITransitionFunction;
//for repeated entries
if(!ar.Contains(Itf))
ar.Add(Itf);
}
DFA1.m_transition_functions=(IList)ar.Clone();
//check for valid functions according to input states
foreach(ITransitionFunction Itf in DFA1.m_transition_functions)
{
if (!DFA1.m_states.Contains(Itf.InputState))
throw new Exception(String.Format("the state with name {0} doesn't exist in states",
Itf.InputState.Name));
if (!DFA1.m_states.Contains(Itf.OutputState))
throw new Exception(String.Format("the state with name {0} doesn't exist in states",
Itf.OutputState.Name));
if(!DFA1.m_symbols.Contains(Itf.InputSymbol))
throw new Exception(String.Format("the symbol with name {0} doesn't exist in symbols",
Itf.InputSymbol.ToString()));
}
//check whether it is a deterministic DFA or it is a NFA
foreach(ITransitionFunction Itf1 in DFA1.m_transition_functions)
foreach(ITransitionFunction Itf2 in DFA1.m_transition_functions)
if(Itf2.InputState==Itf1.InputState && Itf2.InputSymbol==Itf1.InputSymbol
&& Itf1.OutputState!=Itf2.OutputState)
throw new Exception("this is not a determenistic DFA");
}
}
}using that ArrayList states=new ArrayList();
states.Add(new State("A"));
states.Add(new State("B"));
states.Add(new State("C",true));
ArrayList symbols=new ArrayList();
symbols.Add('a');
symbols.Add('b');
symbols.Add('c');
TransitionFunction tf=new TransitionFunction((State)states[2],(State)states[1],'a');
TransitionFunction tf1=new TransitionFunction((State)states[2],(State)states[1],'c');
ArrayList functions=new ArrayList();
functions.Add(tf);
functions.Add(tf1);
DFA dfa=new DFA(states,symbols,(State)states[0],(State)states[2],functions);what a bad implemetation I had done :D
write your own version.

[ponaka_aruna]

thanq,can u plz suggest an algorithm for this as i wud b implementing in C.