http://bezensek.com/blog/2014/08/13/deterministic-finite-state-machine-implementation-in-c-number/
Wednesday, 29 November 2017
DFA in C#
using System;
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
/// <summary>
/// Implements a deterministic finite automata (DFA)
/// </summary>
class DFA
{
// Start state
public state start;
// Set of final states
public Set<state> final;
// Transition table
public SCG.SortedList<KeyValuePair<state, input>, state> transTable;
public DFA()
{
final = new Set<state>();
transTable = new SCG.SortedList<KeyValuePair<state, input>, state>(new Comparer());
}
public string Simulate(string @in)
{
state curState = start;
CharEnumerator i = @in.GetEnumerator();
while(i.MoveNext())
{
KeyValuePair<state, input> transition = new KeyValuePair<state, input>(curState, i.Current);
if(!transTable.ContainsKey(transition))
return "Rejected";
curState = transTable[transition];
}
if(final.Contains(curState))
return "Accepted";
else
return "Rejected";
}
public void Show()
{
Console.Write("DFA start state: {0}\n", start);
Console.Write("DFA final state(s): ");
SCG.IEnumerator<state> iE = final.GetEnumerator();
while(iE.MoveNext())
Console.Write(iE.Current + " ");
Console.Write("\n\n");
foreach(SCG.KeyValuePair<KeyValuePair<state, input>, state> kvp in transTable)
Console.Write("Trans[{0}, {1}] = {2}\n", kvp.Key.Key, kvp.Key.Value, kvp.Value);
}
}
/// <summary>
/// Implements a comparer that suits the transTable SordedList
/// </summary>
public class Comparer : SCG.IComparer<KeyValuePair<state, input>>
{
public int Compare(KeyValuePair<state, input> transition1, KeyValuePair<state, input> transition2)
{
if(transition1.Key == transition2.Key)
return transition1.Value.CompareTo(transition2.Value);
else
return transition1.Key.CompareTo(transition2.Key);
}
}
}
As you see, a DFA has 3 variables: a start state, a set of final states and a transition table that maps transitions between states.
Below I present the SubsetMachine class that is responsible for the hard work of extracting an equivalent DFA from a given NFA:
//
// Regular Expression Engine C# Sample Application
// 2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
// UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//
// This program sample was developed and turned in as a term paper for Lab. of
// Compilers Construction. It was based on the source code provided by Eli Bendersky
// [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//
using System;
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
class SubsetMachine
{
private static int num = 0;
/// <summary>
/// Subset machine that employs the powerset construction or subset construction algorithm.
/// It creates a DFA that recognizes the same language as the given NFA.
/// </summary>
public static DFA SubsetConstruct(NFA nfa)
{
DFA dfa = new DFA();
// Sets of NFA states which is represented by some DFA state
Set<Set<state>> markedStates = new Set<Set<state>>();
Set<Set<state>> unmarkedStates = new Set<Set<state>>();
// Gives a number to each state in the DFA
HashDictionary<Set<state>, state> dfaStateNum = new HashDictionary<Set<state>, state>();
Set<state> nfaInitial = new Set<state>();
nfaInitial.Add(nfa.initial);
// Initially, EpsilonClosure(nfa.initial) is the only state in the DFAs states and it's unmarked.
Set<state> first = EpsilonClosure(nfa, nfaInitial);
unmarkedStates.Add(first);
// The initial dfa state
state dfaInitial = GenNewState();
dfaStateNum[first] = dfaInitial;
dfa.start = dfaInitial;
while(unmarkedStates.Count != 0)
{
// Takes out one unmarked state and posteriorly mark it.
Set<state> aState = unmarkedStates.Choose();
// Removes from the unmarked set.
unmarkedStates.Remove(aState);
// Inserts into the marked set.
markedStates.Add(aState);
// If this state contains the NFA's final state, add it to the DFA's set of
// final states.
if(aState.Contains(nfa.final))
dfa.final.Add(dfaStateNum[aState]);
SCG.IEnumerator<input> iE = nfa.inputs.GetEnumerator();
// For each input symbol the nfa knows...
while(iE.MoveNext())
{
// Next state
Set<state> next = EpsilonClosure(nfa, nfa.Move(aState, iE.Current));
// If we haven't examined this state before, add it to the unmarkedStates and make up a new number for it.
if(!unmarkedStates.Contains(next) && !markedStates.Contains(next))
{
unmarkedStates.Add(next);
dfaStateNum.Add(next, GenNewState());
}
KeyValuePair<state, input> transition = new KeyValuePair<state, input>();
transition.Key = dfaStateNum[aState];
transition.Value = iE.Current;
dfa.transTable[transition] = dfaStateNum[next];
}
}
return dfa;
}
/// <summary>
/// Builds the Epsilon closure of states for the given NFA
/// </summary>
/// <param name="nfa"></param>
/// <param name="states"></param>
/// <returns></returns>
static Set<state> EpsilonClosure(NFA nfa, Set<state> states)
{
// Push all states onto a stack
SCG.Stack<state> uncheckedStack = new SCG.Stack<state>(states);
// Initialize EpsilonClosure(states) to states
Set<state> epsilonClosure = states;
while(uncheckedStack.Count != 0)
{
// Pop state t, the top element, off the stack
state t = uncheckedStack.Pop();
int i = 0;
// For each state u with an edge from t to u labeled Epsilon
foreach(input input in nfa.transTable[t])
{
if(input == (char)NFA.Constants.Epsilon)
{
state u = Array.IndexOf(nfa.transTable[t], input, i);
// If u is not already in epsilonClosure, add it and push it onto stack
if(!epsilonClosure.Contains(u))
{
epsilonClosure.Add(u);
uncheckedStack.Push(u);
}
}
i = i + 1;
}
}
return epsilonClosure;
}
/// <summary>
/// Creates unique state numbers for DFA states
/// </summary>
/// <returns></returns>
private static state GenNewState()
{
return num++;
}
}
}
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
/// <summary>
/// Implements a deterministic finite automata (DFA)
/// </summary>
class DFA
{
// Start state
public state start;
// Set of final states
public Set<state> final;
// Transition table
public SCG.SortedList<KeyValuePair<state, input>, state> transTable;
public DFA()
{
final = new Set<state>();
transTable = new SCG.SortedList<KeyValuePair<state, input>, state>(new Comparer());
}
public string Simulate(string @in)
{
state curState = start;
CharEnumerator i = @in.GetEnumerator();
while(i.MoveNext())
{
KeyValuePair<state, input> transition = new KeyValuePair<state, input>(curState, i.Current);
if(!transTable.ContainsKey(transition))
return "Rejected";
curState = transTable[transition];
}
if(final.Contains(curState))
return "Accepted";
else
return "Rejected";
}
public void Show()
{
Console.Write("DFA start state: {0}\n", start);
Console.Write("DFA final state(s): ");
SCG.IEnumerator<state> iE = final.GetEnumerator();
while(iE.MoveNext())
Console.Write(iE.Current + " ");
Console.Write("\n\n");
foreach(SCG.KeyValuePair<KeyValuePair<state, input>, state> kvp in transTable)
Console.Write("Trans[{0}, {1}] = {2}\n", kvp.Key.Key, kvp.Key.Value, kvp.Value);
}
}
/// <summary>
/// Implements a comparer that suits the transTable SordedList
/// </summary>
public class Comparer : SCG.IComparer<KeyValuePair<state, input>>
{
public int Compare(KeyValuePair<state, input> transition1, KeyValuePair<state, input> transition2)
{
if(transition1.Key == transition2.Key)
return transition1.Value.CompareTo(transition2.Value);
else
return transition1.Key.CompareTo(transition2.Key);
}
}
}
As you see, a DFA has 3 variables: a start state, a set of final states and a transition table that maps transitions between states.
Below I present the SubsetMachine class that is responsible for the hard work of extracting an equivalent DFA from a given NFA:
//
// Regular Expression Engine C# Sample Application
// 2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
// UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//
// This program sample was developed and turned in as a term paper for Lab. of
// Compilers Construction. It was based on the source code provided by Eli Bendersky
// [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//
using System;
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
class SubsetMachine
{
private static int num = 0;
/// <summary>
/// Subset machine that employs the powerset construction or subset construction algorithm.
/// It creates a DFA that recognizes the same language as the given NFA.
/// </summary>
public static DFA SubsetConstruct(NFA nfa)
{
DFA dfa = new DFA();
// Sets of NFA states which is represented by some DFA state
Set<Set<state>> markedStates = new Set<Set<state>>();
Set<Set<state>> unmarkedStates = new Set<Set<state>>();
// Gives a number to each state in the DFA
HashDictionary<Set<state>, state> dfaStateNum = new HashDictionary<Set<state>, state>();
Set<state> nfaInitial = new Set<state>();
nfaInitial.Add(nfa.initial);
// Initially, EpsilonClosure(nfa.initial) is the only state in the DFAs states and it's unmarked.
Set<state> first = EpsilonClosure(nfa, nfaInitial);
unmarkedStates.Add(first);
// The initial dfa state
state dfaInitial = GenNewState();
dfaStateNum[first] = dfaInitial;
dfa.start = dfaInitial;
while(unmarkedStates.Count != 0)
{
// Takes out one unmarked state and posteriorly mark it.
Set<state> aState = unmarkedStates.Choose();
// Removes from the unmarked set.
unmarkedStates.Remove(aState);
// Inserts into the marked set.
markedStates.Add(aState);
// If this state contains the NFA's final state, add it to the DFA's set of
// final states.
if(aState.Contains(nfa.final))
dfa.final.Add(dfaStateNum[aState]);
SCG.IEnumerator<input> iE = nfa.inputs.GetEnumerator();
// For each input symbol the nfa knows...
while(iE.MoveNext())
{
// Next state
Set<state> next = EpsilonClosure(nfa, nfa.Move(aState, iE.Current));
// If we haven't examined this state before, add it to the unmarkedStates and make up a new number for it.
if(!unmarkedStates.Contains(next) && !markedStates.Contains(next))
{
unmarkedStates.Add(next);
dfaStateNum.Add(next, GenNewState());
}
KeyValuePair<state, input> transition = new KeyValuePair<state, input>();
transition.Key = dfaStateNum[aState];
transition.Value = iE.Current;
dfa.transTable[transition] = dfaStateNum[next];
}
}
return dfa;
}
/// <summary>
/// Builds the Epsilon closure of states for the given NFA
/// </summary>
/// <param name="nfa"></param>
/// <param name="states"></param>
/// <returns></returns>
static Set<state> EpsilonClosure(NFA nfa, Set<state> states)
{
// Push all states onto a stack
SCG.Stack<state> uncheckedStack = new SCG.Stack<state>(states);
// Initialize EpsilonClosure(states) to states
Set<state> epsilonClosure = states;
while(uncheckedStack.Count != 0)
{
// Pop state t, the top element, off the stack
state t = uncheckedStack.Pop();
int i = 0;
// For each state u with an edge from t to u labeled Epsilon
foreach(input input in nfa.transTable[t])
{
if(input == (char)NFA.Constants.Epsilon)
{
state u = Array.IndexOf(nfa.transTable[t], input, i);
// If u is not already in epsilonClosure, add it and push it onto stack
if(!epsilonClosure.Contains(u))
{
epsilonClosure.Add(u);
uncheckedStack.Push(u);
}
}
i = i + 1;
}
}
return epsilonClosure;
}
/// <summary>
/// Creates unique state numbers for DFA states
/// </summary>
/// <returns></returns>
private static state GenNewState()
{
return num++;
}
}
}
NFA in C#
using System;
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
/// <summary>
/// Implements a non-deterministic finite automata
/// </summary>
class NFA
{
public state initial;
public state final;
private int size;
// Inputs this NFA responds to
public SortedArray<input> inputs;
public input[][] transTable;
/// <summary>
/// Provides default values for epsilon and none
/// </summary>
public enum Constants
{
Epsilon = 'ε',
None = '\0'
}
public NFA(NFA nfa)
{
initial = nfa.initial;
final = nfa.final;
size = nfa.size;
inputs = nfa.inputs;
transTable = nfa.transTable;
}
/// <summary>
/// Constructed with the NFA size (amount of states), the initial state and the
/// final state
/// </summary>
/// <param name="size_">Amount of states.</param>
/// <param name="initial_">Initial state.</param>
/// <param name="final_">Final state.</param>
public NFA(int size_, state initial_, state final_)
{
initial = initial_;
final = final_;
size = size_;
IsLegalState(initial);
IsLegalState(final);
inputs = new SortedArray<input>();
// Initializes transTable with an "empty graph", no transitions between its
// states
transTable = new input[size][];
for(int i = 0; i < size; ++i)
transTable[i] = new input[size];
}
public bool IsLegalState(state s)
{
// We have 'size' states, numbered 0 to size-1
if(s < 0 || s >= size)
return false;
return true;
}
/// <summary>
/// Adds a transition between two states.
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <param name="in"></param>
public void AddTrans(state from, state to, input @in)
{
IsLegalState(from);
IsLegalState(to);
transTable[from][to] = @in;
if(@in != (char)Constants.Epsilon)
inputs.Add(@in);
}
/// <summary>
/// Fills states 0 up to other.size with other's states.
/// </summary>
/// <param name="other"></param>
public void FillStates(NFA other)
{
for(state i = 0; i < other.size; ++i)
for(state j = 0; j < other.size; ++j)
transTable[i][j] = other.transTable[i][j];
SCG.IEnumerator<input> cE = other.inputs.GetEnumerator();
while(cE.MoveNext())
inputs.Add(cE.Current);
}
/// <summary>
/// Renames all the NFA's states. For each nfa state: number += shift.
/// Functionally, this doesn't affect the NFA, it only makes it larger and renames
/// its states.
/// </summary>
/// <param name="shift"></param>
public void ShiftStates(int shift)
{
int newSize = size + shift;
if(shift < 1)
return;
// Creates a new, empty transition table (of the new size).
input[][] newTransTable = new input[newSize][];
for(int i = 0; i < newSize; ++i)
newTransTable[i] = new input[newSize];
// Copies all the transitions to the new table, at their new locations.
for(state i = 0; i < size; ++i)
for(state j = 0; j < size; ++j)
newTransTable[i + shift][j + shift] = transTable[i][j];
// Updates the NFA members.
size = newSize;
initial += shift;
final += shift;
transTable = newTransTable;
}
/// <summary>
/// Appends a new, empty state to the NFA.
/// </summary>
public void AppendEmptyState()
{
transTable = Resize(transTable, size + 1);
size += 1;
}
private static input[][] Resize(input[][] transTable, int newSize)
{
input[][] newTransTable = new input[newSize][];
for(int i = 0; i < newSize; ++i)
newTransTable[i] = new input[newSize];
for(int i = 0; i <= transTable.Length - 1; i++)
for(int j = 0; j <= transTable[i].Length - 1; j++)
{
if(transTable[i][j] != '\0')
newTransTable[i][j] = transTable[i][j];
}
return newTransTable;
}
/// <summary>
/// Returns a set of NFA states from which there is a transition on input symbol
/// inp from some state s in states.
/// </summary>
/// <param name="states"></param>
/// <param name="inp"></param>
/// <returns></returns>
public Set<state> Move(Set<state> states, input inp)
{
Set<state> result = new Set<state>();
// For each state in the set of states
foreach(state state in states)
{
int i = 0;
// For each transition from this state
foreach(input input in transTable[state])
{
// If the transition is on input inp, add it to the resulting set
if(input == inp)
{
state u = Array.IndexOf(transTable[state], input, i);
result.Add(u);
}
i = i + 1;
}
}
return result;
}
/// <summary>
/// Prints out the NFA.
/// </summary>
public void Show()
{
Console.WriteLine("This NFA has {0} states: 0 - {1}", size, size - 1);
Console.WriteLine("The initial state is {0}", initial);
Console.WriteLine("The final state is {0}\n", final);
for(state from = 0; from < size; ++from)
{
for(state to = 0; to < size; ++to)
{
input @in = transTable[from][to];
if(@in != (char)Constants.None)
{
Console.Write("Transition from {0} to {1} on input ", from, to);
if(@in == (char)Constants.Epsilon)
Console.Write("Epsilon\n");
else
Console.Write("{0}\n", @in);
}
}
}
Console.Write("\n\n");
}
/// <summary>
///
/// </summary>
/// <param name="tree"></param>
/// <returns></returns>
public static NFA TreeToNFA(ParseTree tree)
{
switch (tree.type)
{
case ParseTree.NodeType.Chr:
return BuildNFABasic(tree.data.Value);
case ParseTree.NodeType.Alter:
return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Concat:
return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Star:
return BuildNFAStar(TreeToNFA(tree.left));
case ParseTree.NodeType.Question:
return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
default:
return null;
}
}
/////////////////////////////////////////////////////////////////
//
// NFA building functions
//
// Using Thompson Construction, build NFAs from basic inputs or
// compositions of other NFAs.
//
/// <summary>
/// Builds a basic, single input NFA
/// </summary>
/// <param name="in"></param>
/// <returns></returns>
public static NFA BuildNFABasic(input @in)
{
NFA basic = new NFA(2, 0, 1);
basic.AddTrans(0, 1, @in);
return basic;
}
/// <summary>
/// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
/// </summary>
/// <param name="nfa1"></param>
/// <param name="nfa2"></param>
/// <returns></returns>
public static NFA BuildNFAAlter(NFA nfa1, NFA nfa2)
{
// How this is done: the new nfa must contain all the states in
// nfa1 and nfa2, plus a new initial and final states.
// First will come the new initial state, then nfa1's states, then
// nfa2's states, then the new final state
// make room for the new initial state
nfa1.ShiftStates(1);
// make room for nfa1
nfa2.ShiftStates(nfa1.size);
// create a new nfa and initialize it with (the shifted) nfa2
NFA newNFA = new NFA(nfa2);
// nfa1's states take their places in new_nfa
newNFA.FillStates(nfa1);
// Set new initial state and the transitions from it
newNFA.AddTrans(0, nfa1.initial, (char)Constants.Epsilon);
newNFA.AddTrans(0, nfa2.initial, (char)Constants.Epsilon);
newNFA.initial = 0;
// Make up space for the new final state
newNFA.AppendEmptyState();
// Set new final state
newNFA.final = newNFA.size - 1;
newNFA.AddTrans(nfa1.final, newNFA.final, (char)Constants.Epsilon);
newNFA.AddTrans(nfa2.final, newNFA.final, (char)Constants.Epsilon);
return newNFA;
}
/// <summary>
/// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
/// </summary>
/// <param name="nfa1"></param>
/// <param name="nfa2"></param>
/// <returns></returns>
public static NFA BuildNFAConcat(NFA nfa1, NFA nfa2)
{
// How this is done: First will come nfa1, then nfa2 (its initial state replaced
// with nfa1's final state)
nfa2.ShiftStates(nfa1.size - 1);
// Creates a new NFA and initialize it with (the shifted) nfa2
NFA newNFA = new NFA(nfa2);
// nfa1's states take their places in newNFA
// note: nfa1's final state overwrites nfa2's initial state,
// thus we get the desired merge automatically (the transition
// from nfa2's initial state now transits from nfa1's final state)
newNFA.FillStates(nfa1);
// Sets the new initial state (the final state stays nfa2's final state,
// and was already copied)
newNFA.initial = nfa1.initial;
return newNFA;
}
/// <summary>
/// Builds a star (kleene closure) of nfa (nfa*)
/// How this is done: First will come the new initial state, then NFA, then the new final state
/// </summary>
/// <param name="nfa"></param>
/// <returns></returns>
public static NFA BuildNFAStar(NFA nfa)
{
// Makes room for the new initial state
nfa.ShiftStates(1);
// Makes room for the new final state
nfa.AppendEmptyState();
// Adds new transitions
nfa.AddTrans(nfa.final, nfa.initial, (char)Constants.Epsilon);
nfa.AddTrans(0, nfa.initial, (char)Constants.Epsilon);
nfa.AddTrans(nfa.final, nfa.size - 1, (char)Constants.Epsilon);
nfa.AddTrans(0, nfa.size - 1, (char)Constants.Epsilon);
nfa.initial = 0;
nfa.final = nfa.size - 1;
return nfa;
}
}
}
We pass the parse tree (see last post) to a function responsible for converting the parse tree to an NFA.
private NFA TreeToNFA(ParseTree tree)
{
switch(tree.type)
{
case ParseTree.NodeType.Chr:
return BuildNFABasic(tree.data.Value);
case ParseTree.NodeType.Alter:
return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Concat:
return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Star:
return BuildNFAStar(TreeToNFA(tree.left));
case ParseTree.NodeType.Question:
return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
default:
return null;
}
}
using SCG = System.Collections.Generic;
using C5;
using state = System.Int32;
using input = System.Char;
namespace RegularExpressionEngine
{
/// <summary>
/// Implements a non-deterministic finite automata
/// </summary>
class NFA
{
public state initial;
public state final;
private int size;
// Inputs this NFA responds to
public SortedArray<input> inputs;
public input[][] transTable;
/// <summary>
/// Provides default values for epsilon and none
/// </summary>
public enum Constants
{
Epsilon = 'ε',
None = '\0'
}
public NFA(NFA nfa)
{
initial = nfa.initial;
final = nfa.final;
size = nfa.size;
inputs = nfa.inputs;
transTable = nfa.transTable;
}
/// <summary>
/// Constructed with the NFA size (amount of states), the initial state and the
/// final state
/// </summary>
/// <param name="size_">Amount of states.</param>
/// <param name="initial_">Initial state.</param>
/// <param name="final_">Final state.</param>
public NFA(int size_, state initial_, state final_)
{
initial = initial_;
final = final_;
size = size_;
IsLegalState(initial);
IsLegalState(final);
inputs = new SortedArray<input>();
// Initializes transTable with an "empty graph", no transitions between its
// states
transTable = new input[size][];
for(int i = 0; i < size; ++i)
transTable[i] = new input[size];
}
public bool IsLegalState(state s)
{
// We have 'size' states, numbered 0 to size-1
if(s < 0 || s >= size)
return false;
return true;
}
/// <summary>
/// Adds a transition between two states.
/// </summary>
/// <param name="from"></param>
/// <param name="to"></param>
/// <param name="in"></param>
public void AddTrans(state from, state to, input @in)
{
IsLegalState(from);
IsLegalState(to);
transTable[from][to] = @in;
if(@in != (char)Constants.Epsilon)
inputs.Add(@in);
}
/// <summary>
/// Fills states 0 up to other.size with other's states.
/// </summary>
/// <param name="other"></param>
public void FillStates(NFA other)
{
for(state i = 0; i < other.size; ++i)
for(state j = 0; j < other.size; ++j)
transTable[i][j] = other.transTable[i][j];
SCG.IEnumerator<input> cE = other.inputs.GetEnumerator();
while(cE.MoveNext())
inputs.Add(cE.Current);
}
/// <summary>
/// Renames all the NFA's states. For each nfa state: number += shift.
/// Functionally, this doesn't affect the NFA, it only makes it larger and renames
/// its states.
/// </summary>
/// <param name="shift"></param>
public void ShiftStates(int shift)
{
int newSize = size + shift;
if(shift < 1)
return;
// Creates a new, empty transition table (of the new size).
input[][] newTransTable = new input[newSize][];
for(int i = 0; i < newSize; ++i)
newTransTable[i] = new input[newSize];
// Copies all the transitions to the new table, at their new locations.
for(state i = 0; i < size; ++i)
for(state j = 0; j < size; ++j)
newTransTable[i + shift][j + shift] = transTable[i][j];
// Updates the NFA members.
size = newSize;
initial += shift;
final += shift;
transTable = newTransTable;
}
/// <summary>
/// Appends a new, empty state to the NFA.
/// </summary>
public void AppendEmptyState()
{
transTable = Resize(transTable, size + 1);
size += 1;
}
private static input[][] Resize(input[][] transTable, int newSize)
{
input[][] newTransTable = new input[newSize][];
for(int i = 0; i < newSize; ++i)
newTransTable[i] = new input[newSize];
for(int i = 0; i <= transTable.Length - 1; i++)
for(int j = 0; j <= transTable[i].Length - 1; j++)
{
if(transTable[i][j] != '\0')
newTransTable[i][j] = transTable[i][j];
}
return newTransTable;
}
/// <summary>
/// Returns a set of NFA states from which there is a transition on input symbol
/// inp from some state s in states.
/// </summary>
/// <param name="states"></param>
/// <param name="inp"></param>
/// <returns></returns>
public Set<state> Move(Set<state> states, input inp)
{
Set<state> result = new Set<state>();
// For each state in the set of states
foreach(state state in states)
{
int i = 0;
// For each transition from this state
foreach(input input in transTable[state])
{
// If the transition is on input inp, add it to the resulting set
if(input == inp)
{
state u = Array.IndexOf(transTable[state], input, i);
result.Add(u);
}
i = i + 1;
}
}
return result;
}
/// <summary>
/// Prints out the NFA.
/// </summary>
public void Show()
{
Console.WriteLine("This NFA has {0} states: 0 - {1}", size, size - 1);
Console.WriteLine("The initial state is {0}", initial);
Console.WriteLine("The final state is {0}\n", final);
for(state from = 0; from < size; ++from)
{
for(state to = 0; to < size; ++to)
{
input @in = transTable[from][to];
if(@in != (char)Constants.None)
{
Console.Write("Transition from {0} to {1} on input ", from, to);
if(@in == (char)Constants.Epsilon)
Console.Write("Epsilon\n");
else
Console.Write("{0}\n", @in);
}
}
}
Console.Write("\n\n");
}
/// <summary>
///
/// </summary>
/// <param name="tree"></param>
/// <returns></returns>
public static NFA TreeToNFA(ParseTree tree)
{
switch (tree.type)
{
case ParseTree.NodeType.Chr:
return BuildNFABasic(tree.data.Value);
case ParseTree.NodeType.Alter:
return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Concat:
return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Star:
return BuildNFAStar(TreeToNFA(tree.left));
case ParseTree.NodeType.Question:
return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
default:
return null;
}
}
/////////////////////////////////////////////////////////////////
//
// NFA building functions
//
// Using Thompson Construction, build NFAs from basic inputs or
// compositions of other NFAs.
//
/// <summary>
/// Builds a basic, single input NFA
/// </summary>
/// <param name="in"></param>
/// <returns></returns>
public static NFA BuildNFABasic(input @in)
{
NFA basic = new NFA(2, 0, 1);
basic.AddTrans(0, 1, @in);
return basic;
}
/// <summary>
/// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
/// </summary>
/// <param name="nfa1"></param>
/// <param name="nfa2"></param>
/// <returns></returns>
public static NFA BuildNFAAlter(NFA nfa1, NFA nfa2)
{
// How this is done: the new nfa must contain all the states in
// nfa1 and nfa2, plus a new initial and final states.
// First will come the new initial state, then nfa1's states, then
// nfa2's states, then the new final state
// make room for the new initial state
nfa1.ShiftStates(1);
// make room for nfa1
nfa2.ShiftStates(nfa1.size);
// create a new nfa and initialize it with (the shifted) nfa2
NFA newNFA = new NFA(nfa2);
// nfa1's states take their places in new_nfa
newNFA.FillStates(nfa1);
// Set new initial state and the transitions from it
newNFA.AddTrans(0, nfa1.initial, (char)Constants.Epsilon);
newNFA.AddTrans(0, nfa2.initial, (char)Constants.Epsilon);
newNFA.initial = 0;
// Make up space for the new final state
newNFA.AppendEmptyState();
// Set new final state
newNFA.final = newNFA.size - 1;
newNFA.AddTrans(nfa1.final, newNFA.final, (char)Constants.Epsilon);
newNFA.AddTrans(nfa2.final, newNFA.final, (char)Constants.Epsilon);
return newNFA;
}
/// <summary>
/// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
/// </summary>
/// <param name="nfa1"></param>
/// <param name="nfa2"></param>
/// <returns></returns>
public static NFA BuildNFAConcat(NFA nfa1, NFA nfa2)
{
// How this is done: First will come nfa1, then nfa2 (its initial state replaced
// with nfa1's final state)
nfa2.ShiftStates(nfa1.size - 1);
// Creates a new NFA and initialize it with (the shifted) nfa2
NFA newNFA = new NFA(nfa2);
// nfa1's states take their places in newNFA
// note: nfa1's final state overwrites nfa2's initial state,
// thus we get the desired merge automatically (the transition
// from nfa2's initial state now transits from nfa1's final state)
newNFA.FillStates(nfa1);
// Sets the new initial state (the final state stays nfa2's final state,
// and was already copied)
newNFA.initial = nfa1.initial;
return newNFA;
}
/// <summary>
/// Builds a star (kleene closure) of nfa (nfa*)
/// How this is done: First will come the new initial state, then NFA, then the new final state
/// </summary>
/// <param name="nfa"></param>
/// <returns></returns>
public static NFA BuildNFAStar(NFA nfa)
{
// Makes room for the new initial state
nfa.ShiftStates(1);
// Makes room for the new final state
nfa.AppendEmptyState();
// Adds new transitions
nfa.AddTrans(nfa.final, nfa.initial, (char)Constants.Epsilon);
nfa.AddTrans(0, nfa.initial, (char)Constants.Epsilon);
nfa.AddTrans(nfa.final, nfa.size - 1, (char)Constants.Epsilon);
nfa.AddTrans(0, nfa.size - 1, (char)Constants.Epsilon);
nfa.initial = 0;
nfa.final = nfa.size - 1;
return nfa;
}
}
}
We pass the parse tree (see last post) to a function responsible for converting the parse tree to an NFA.
private NFA TreeToNFA(ParseTree tree)
{
switch(tree.type)
{
case ParseTree.NodeType.Chr:
return BuildNFABasic(tree.data.Value);
case ParseTree.NodeType.Alter:
return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Concat:
return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
case ParseTree.NodeType.Star:
return BuildNFAStar(TreeToNFA(tree.left));
case ParseTree.NodeType.Question:
return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
default:
return null;
}
}
DFA Factory
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
/// <summary>
/// Creates and returns a DFA
/// </summary>
public static class DFAFactory
{
public static DFA BuildDefaultDFA(string alphabet, string states, string transitionFunction, string startingState) {
// Split Parameters for DFA from given strings.
List<Transition> alphabetParameter = Utils.CreateTransitionsFromAlphabet(alphabet);
List<State> statesParameter = Utils.CreateDefaultStatesFromString(states);
// Split transitionFunction string and create transitions to states.
var splittingResult = Utils.SplitParameter(transitionFunction);
for (int i = 0; i < splittingResult.Length; i++)
{
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
//Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
foreach (var state in statesParameter)
{
if (state.StateName.Equals(furtherSplitResult[0]))
{
Transition tempTransition = null;
foreach (var trans in alphabetParameter)
{
if (trans.TransitionName.Equals(furtherSplitResult[1]))
{
tempTransition = trans;
}//if
}//foreach
State tempState = null;
foreach (var stat in statesParameter)
{
if (stat.StateName.Equals(furtherSplitResult[2]))
{
tempState = stat;
}//if
}//foreach
state.AddTransition(tempTransition, tempState);
Console.WriteLine("Added transition " + tempTransition.TransitionName + " leading to state " + tempState.StateName + " in state " + state.StateName + " transitions.");
}//if
}//foreach
}//for
DFA dfa = new DFA(alphabetParameter, statesParameter);
// Assign starting state
foreach(State state in statesParameter){
if(state.StateName.Equals(startingState)){
dfa.CurrentState = state;
}//if
}//foreach
return dfa;
}
//public static DFA BuildDefaultDFA(string alphabet, string states, string transitionTable, string startingStateName)
//{
/*
//Check that the given parameters are valid.
if (alphabet == null || states == null || transitionTable == null || startingStateName == null)
{
Console.WriteLine("ERROR: given parameters to build default dfa are invalid");
return null;
}
//Resolve alphabet from given string.
string[] transitionNames = Utils.ResolveAlphabetFromString(alphabet);
//Check for duplicate alphabet (transition names).
Utils.CheckForDuplicates(transitionNames);
//Create transition parameter for DFA from alphabet.
List<Transition> transitionsParameter = new List<Transition>();
for (int i = 0; i < transitionNames.Length; i++)
{
transitionsParameter.Add(new Transition(transitionNames[i], i));
}
//Resolve states' names
string[] stateNames = Utils.ResolveStatesFromString(states);
//Check for duplicate state names.
Utils.CheckForDuplicates(stateNames);
//Create state parameter for DFA from list of state names.
List<State> statesParameter = new List<State>();
for (int i = 0; i < stateNames.Length; i++)
{
statesParameter.Add(new DefaultState(stateNames[i], i));
}
//Create transitions.
string[] transitionSets = Utils.ResolveTransitionSetsFromString(transitionTable);
//Further split transition sets
for (int i = 0; i < transitionSets.Length; i++)
{
string[] transitionAndState = Utils.ResolveTransitionFromTransitionSet(transitionSets[i]);
State stateToAddTransition = null;
foreach (State state in statesParameter)
{
if (transitionAndState[0].Equals(state.StateName))
{
stateToAddTransition = state;
}//if
}//foreach
Transition transitionToAdd = null;
foreach (Transition transition in transitionsParameter)
{
if (transitionAndState[1].Equals(transition.TransitionName))
{
transitionToAdd = transition;
}//if
}//foreach
State stateToTransit = null;
foreach (State state in statesParameter)
{
if (transitionAndState[2].Equals(state.StateName))
{
stateToTransit = state;
}//if
}//foreach
stateToAddTransition.AddTransition(transitionToAdd, stateToTransit);
}//for
//Define starting state
State startingState = null;
foreach (State state in statesParameter)
{
if (state.StateName.Equals(startingStateName))
{
startingState = state;
}//if
}//foreach
//Build default DFA
DFA defaultDFA = new DFA(transitionsParameter, statesParameter);
defaultDFA.CurrentState = startingState;
return defaultDFA;
*/
//}//BuildDefaultDFA
}//DFAFactory
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
/// <summary>
/// Creates and returns a DFA
/// </summary>
public static class DFAFactory
{
public static DFA BuildDefaultDFA(string alphabet, string states, string transitionFunction, string startingState) {
// Split Parameters for DFA from given strings.
List<Transition> alphabetParameter = Utils.CreateTransitionsFromAlphabet(alphabet);
List<State> statesParameter = Utils.CreateDefaultStatesFromString(states);
// Split transitionFunction string and create transitions to states.
var splittingResult = Utils.SplitParameter(transitionFunction);
for (int i = 0; i < splittingResult.Length; i++)
{
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
//Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
foreach (var state in statesParameter)
{
if (state.StateName.Equals(furtherSplitResult[0]))
{
Transition tempTransition = null;
foreach (var trans in alphabetParameter)
{
if (trans.TransitionName.Equals(furtherSplitResult[1]))
{
tempTransition = trans;
}//if
}//foreach
State tempState = null;
foreach (var stat in statesParameter)
{
if (stat.StateName.Equals(furtherSplitResult[2]))
{
tempState = stat;
}//if
}//foreach
state.AddTransition(tempTransition, tempState);
Console.WriteLine("Added transition " + tempTransition.TransitionName + " leading to state " + tempState.StateName + " in state " + state.StateName + " transitions.");
}//if
}//foreach
}//for
DFA dfa = new DFA(alphabetParameter, statesParameter);
// Assign starting state
foreach(State state in statesParameter){
if(state.StateName.Equals(startingState)){
dfa.CurrentState = state;
}//if
}//foreach
return dfa;
}
//public static DFA BuildDefaultDFA(string alphabet, string states, string transitionTable, string startingStateName)
//{
/*
//Check that the given parameters are valid.
if (alphabet == null || states == null || transitionTable == null || startingStateName == null)
{
Console.WriteLine("ERROR: given parameters to build default dfa are invalid");
return null;
}
//Resolve alphabet from given string.
string[] transitionNames = Utils.ResolveAlphabetFromString(alphabet);
//Check for duplicate alphabet (transition names).
Utils.CheckForDuplicates(transitionNames);
//Create transition parameter for DFA from alphabet.
List<Transition> transitionsParameter = new List<Transition>();
for (int i = 0; i < transitionNames.Length; i++)
{
transitionsParameter.Add(new Transition(transitionNames[i], i));
}
//Resolve states' names
string[] stateNames = Utils.ResolveStatesFromString(states);
//Check for duplicate state names.
Utils.CheckForDuplicates(stateNames);
//Create state parameter for DFA from list of state names.
List<State> statesParameter = new List<State>();
for (int i = 0; i < stateNames.Length; i++)
{
statesParameter.Add(new DefaultState(stateNames[i], i));
}
//Create transitions.
string[] transitionSets = Utils.ResolveTransitionSetsFromString(transitionTable);
//Further split transition sets
for (int i = 0; i < transitionSets.Length; i++)
{
string[] transitionAndState = Utils.ResolveTransitionFromTransitionSet(transitionSets[i]);
State stateToAddTransition = null;
foreach (State state in statesParameter)
{
if (transitionAndState[0].Equals(state.StateName))
{
stateToAddTransition = state;
}//if
}//foreach
Transition transitionToAdd = null;
foreach (Transition transition in transitionsParameter)
{
if (transitionAndState[1].Equals(transition.TransitionName))
{
transitionToAdd = transition;
}//if
}//foreach
State stateToTransit = null;
foreach (State state in statesParameter)
{
if (transitionAndState[2].Equals(state.StateName))
{
stateToTransit = state;
}//if
}//foreach
stateToAddTransition.AddTransition(transitionToAdd, stateToTransit);
}//for
//Define starting state
State startingState = null;
foreach (State state in statesParameter)
{
if (state.StateName.Equals(startingStateName))
{
startingState = state;
}//if
}//foreach
//Build default DFA
DFA defaultDFA = new DFA(transitionsParameter, statesParameter);
defaultDFA.CurrentState = startingState;
return defaultDFA;
*/
//}//BuildDefaultDFA
}//DFAFactory
}
harjoitustyo Program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
class Program
{
// Parameters for default dfa.
private static string _alphabet = "a,b,c"; //names of the transitions.
private static string _states = "A,B,C"; //names of the states.
private static string _transitionFunction = "{A-a-B};{B-a-C};{B-b-A};{C-c-A}"; //Transition functions: for example {A,a,B} means State A has a transition a to state B.
private static string _startingState = "A"; //stating state.
private static DFA dfa;
static void Main(string[] args)
{
Console.WriteLine("Hello and welcome to the DFA generator!");
PrintInstructions();
HandleInput();
//dfa = DFAFactory.BuildDefaultDFA(_alphabet, _states, _transitionFunction, _startingState);
//dfa.PerformTransition("a");
Console.WriteLine("Press any key to continue...");
Console.ReadKey();
}//Main
public static void PrintInstructions() {
Console.WriteLine("Press Esc to exit, u to create a user defined default dfa or g to build pre-defined default dfa.");
}//PrintInstructions
public static void PrintDFAInstructions() {
Console.WriteLine("Press t to transit to state");
}//PrintDFAInstructions
public static void HandleInput() {
if (Console.ReadKey(true).Key == ConsoleKey.Escape) {
//Don't do anything
}
if(Console.ReadKey(true).Key == ConsoleKey.G){
dfa = DFAFactory.BuildDefaultDFA(_alphabet, _states, _transitionFunction, _startingState);
OperateDFA();
}
if (Console.ReadKey(true).Key == ConsoleKey.U) {
//Query user for DFA parameters
Console.WriteLine("Write DFA alphabet in form of symbol,symbol,symbol without spaces between symbols - for example a,b,c");
string alphabet = Console.ReadLine();
Console.WriteLine("Write states in form of State,State,State without spaces between state names - for example A,B,C");
string states = Console.ReadLine();
Console.WriteLine("Write transition function in form of {starting state-transition-goal state};{starting state-transition-goal state} - for example {A-a-B}");
string transitionFunction = Console.ReadLine();
Console.WriteLine("Write the name of the starting state");
string startingState = Console.ReadLine();
//Build default dfa
dfa = DFAFactory.BuildDefaultDFA(alphabet, states,transitionFunction,startingState);
OperateDFA();
}
}//HandleInput
public static void OperateDFA(){
bool isOperating = true;
while(isOperating){
//Print available states
Console.WriteLine("DFA has following states: ");
foreach(State state in dfa.States){
Console.WriteLine(state.StateName);
}
//Print available transitions
Console.WriteLine("DFA has following transitions: ");
foreach(Transition transition in dfa.Alphabet){
Console.WriteLine(transition.TransitionName);
}
//Ask for user input
Console.WriteLine("Enter transition's name");
dfa.PerformTransition(Console.ReadLine());
Console.WriteLine("Current state is: " + dfa.CurrentState.StateName);
Console.WriteLine("Press Esc to quit or enter transition's name");
if (Console.ReadKey(true).Key == ConsoleKey.Escape)
{
isOperating = false;
}//if
}//while
}//OperateDFA
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
class Program
{
// Parameters for default dfa.
private static string _alphabet = "a,b,c"; //names of the transitions.
private static string _states = "A,B,C"; //names of the states.
private static string _transitionFunction = "{A-a-B};{B-a-C};{B-b-A};{C-c-A}"; //Transition functions: for example {A,a,B} means State A has a transition a to state B.
private static string _startingState = "A"; //stating state.
private static DFA dfa;
static void Main(string[] args)
{
Console.WriteLine("Hello and welcome to the DFA generator!");
PrintInstructions();
HandleInput();
//dfa = DFAFactory.BuildDefaultDFA(_alphabet, _states, _transitionFunction, _startingState);
//dfa.PerformTransition("a");
Console.WriteLine("Press any key to continue...");
Console.ReadKey();
}//Main
public static void PrintInstructions() {
Console.WriteLine("Press Esc to exit, u to create a user defined default dfa or g to build pre-defined default dfa.");
}//PrintInstructions
public static void PrintDFAInstructions() {
Console.WriteLine("Press t to transit to state");
}//PrintDFAInstructions
public static void HandleInput() {
if (Console.ReadKey(true).Key == ConsoleKey.Escape) {
//Don't do anything
}
if(Console.ReadKey(true).Key == ConsoleKey.G){
dfa = DFAFactory.BuildDefaultDFA(_alphabet, _states, _transitionFunction, _startingState);
OperateDFA();
}
if (Console.ReadKey(true).Key == ConsoleKey.U) {
//Query user for DFA parameters
Console.WriteLine("Write DFA alphabet in form of symbol,symbol,symbol without spaces between symbols - for example a,b,c");
string alphabet = Console.ReadLine();
Console.WriteLine("Write states in form of State,State,State without spaces between state names - for example A,B,C");
string states = Console.ReadLine();
Console.WriteLine("Write transition function in form of {starting state-transition-goal state};{starting state-transition-goal state} - for example {A-a-B}");
string transitionFunction = Console.ReadLine();
Console.WriteLine("Write the name of the starting state");
string startingState = Console.ReadLine();
//Build default dfa
dfa = DFAFactory.BuildDefaultDFA(alphabet, states,transitionFunction,startingState);
OperateDFA();
}
}//HandleInput
public static void OperateDFA(){
bool isOperating = true;
while(isOperating){
//Print available states
Console.WriteLine("DFA has following states: ");
foreach(State state in dfa.States){
Console.WriteLine(state.StateName);
}
//Print available transitions
Console.WriteLine("DFA has following transitions: ");
foreach(Transition transition in dfa.Alphabet){
Console.WriteLine(transition.TransitionName);
}
//Ask for user input
Console.WriteLine("Enter transition's name");
dfa.PerformTransition(Console.ReadLine());
Console.WriteLine("Current state is: " + dfa.CurrentState.StateName);
Console.WriteLine("Press Esc to quit or enter transition's name");
if (Console.ReadKey(true).Key == ConsoleKey.Escape)
{
isOperating = false;
}//if
}//while
}//OperateDFA
}
}
States
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public abstract class State
{
// Class variables
protected string _stateName;
public string StateName { get { return _stateName; } }
protected int _stateID;
public int StateID { get { return _stateID; } }
protected Dictionary<int, int> stateTransitions = new Dictionary<int, int>();
public Dictionary<int, int> StateTransitions { get { return stateTransitions; } }
public State(string stateName, int stateID)
{
this._stateName = stateName;
this._stateID = stateID;
}
// Class Behaviour
public void AddTransition(Transition transition, State state)
{
// Check that the given parameters are valid.
if (transition==null || state == null)
{
Console.WriteLine("ERROR in State AddTransition: given parameters are not valid!");
return;
}//if
// Check for duplicates - a deterministic finite automata cannot have a transition with a same id multiple times.
if (stateTransitions.ContainsKey(transition.TransitionID))
{
Console.WriteLine("ERROR in State AddTransition: transition with id of " + transition.TransitionID + " is already included in state's transitions!");
return;
}
// Add transition
stateTransitions.Add(transition.TransitionID, state._stateID);
}//AddTransition
public void RemoveTransition(Transition transition)
{
//Check whether given parameter is valid.
if (isTransitionValid(transition)) { }
//Check whether given transitions exists and remove transition from state
if (stateTransitions.ContainsKey(transition.TransitionID))
{
stateTransitions.Remove(transition.TransitionID);
Console.WriteLine("Removed transition with the id of " + transition.TransitionID.ToString() +
" and name of " + transition.TransitionName + " from state " + _stateName + " with id " + _stateID);
return;
}//if
//If transition wasn't found, write error
Console.WriteLine("ERROR in RemoveTransition: transition was not found in state's transitions");
}// RemoveTransition
public int GetStateToTransit(Transition transition)
{
// Check whether given parameter is valid
if (isTransitionValid(transition)) { }
// Check whether state has transition and return state id the transition is pointing to
if (stateTransitions.ContainsKey(transition.TransitionID))
{
return stateTransitions[transition.TransitionID];
}
// if transition wasn't found, return -1, which is default id for non-existing state. In other words transition points to state itself.
return -1;
}//GetStateToTransit
public virtual void stateBehaviour()
{
Console.WriteLine("This is default state behaviour!");
}
public virtual void onEnteringState()
{
Console.WriteLine("Activing state with id of " + _stateID.ToString() + " and name of " + _stateName);
}
public virtual void onLeavingState()
{
Console.WriteLine("Deactiving state with id of " + _stateID.ToString() + " and name of " + _stateName);
}
private bool isTransitionValid(Transition transition)
{
if (transition == null)
{
Console.WriteLine("ERROR: given transition parameter is null");
return false;
}//if
return true;
}//isTransitionValid
}//State
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public abstract class State
{
// Class variables
protected string _stateName;
public string StateName { get { return _stateName; } }
protected int _stateID;
public int StateID { get { return _stateID; } }
protected Dictionary<int, int> stateTransitions = new Dictionary<int, int>();
public Dictionary<int, int> StateTransitions { get { return stateTransitions; } }
public State(string stateName, int stateID)
{
this._stateName = stateName;
this._stateID = stateID;
}
// Class Behaviour
public void AddTransition(Transition transition, State state)
{
// Check that the given parameters are valid.
if (transition==null || state == null)
{
Console.WriteLine("ERROR in State AddTransition: given parameters are not valid!");
return;
}//if
// Check for duplicates - a deterministic finite automata cannot have a transition with a same id multiple times.
if (stateTransitions.ContainsKey(transition.TransitionID))
{
Console.WriteLine("ERROR in State AddTransition: transition with id of " + transition.TransitionID + " is already included in state's transitions!");
return;
}
// Add transition
stateTransitions.Add(transition.TransitionID, state._stateID);
}//AddTransition
public void RemoveTransition(Transition transition)
{
//Check whether given parameter is valid.
if (isTransitionValid(transition)) { }
//Check whether given transitions exists and remove transition from state
if (stateTransitions.ContainsKey(transition.TransitionID))
{
stateTransitions.Remove(transition.TransitionID);
Console.WriteLine("Removed transition with the id of " + transition.TransitionID.ToString() +
" and name of " + transition.TransitionName + " from state " + _stateName + " with id " + _stateID);
return;
}//if
//If transition wasn't found, write error
Console.WriteLine("ERROR in RemoveTransition: transition was not found in state's transitions");
}// RemoveTransition
public int GetStateToTransit(Transition transition)
{
// Check whether given parameter is valid
if (isTransitionValid(transition)) { }
// Check whether state has transition and return state id the transition is pointing to
if (stateTransitions.ContainsKey(transition.TransitionID))
{
return stateTransitions[transition.TransitionID];
}
// if transition wasn't found, return -1, which is default id for non-existing state. In other words transition points to state itself.
return -1;
}//GetStateToTransit
public virtual void stateBehaviour()
{
Console.WriteLine("This is default state behaviour!");
}
public virtual void onEnteringState()
{
Console.WriteLine("Activing state with id of " + _stateID.ToString() + " and name of " + _stateName);
}
public virtual void onLeavingState()
{
Console.WriteLine("Deactiving state with id of " + _stateID.ToString() + " and name of " + _stateName);
}
private bool isTransitionValid(Transition transition)
{
if (transition == null)
{
Console.WriteLine("ERROR: given transition parameter is null");
return false;
}//if
return true;
}//isTransitionValid
}//State
}
Tests
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace harjoitustyo
{
class Tests
{
// Test variables;
private string _alphabet = "a,b,c"; //names of the transitions
private string _states = "A,B,C"; //names of the states
private string _transitionFunction = "{A-a-B};{B-a-C};{B-b-A};{C-c-A}"; //Transition functions: for example {A,a,B} means State A has a transition a to state B.
private string _startingState = "A";
/// <summary>
/// Drives a set of tests.
/// </summary>
public void DriveTests() {
//Utils component tests
//TestParameterSplitting();
//TestStateAndTransitionsSplitting();
//TestParameterDuplicates();
//Transition component tests
//CreateTestTransitions();
//CreateTestTransitionsFromString();
//State component tests
//CreateTestStates();
//CreateTestStatesFromString();
//TryAddingTransitionsToState();
//TryRemovingTransitionsFromState();
//TryGettingStateToTransit();
//DFA component tests
//CreateDFA();
//TryAddingStatesToDFA();
//TryRemovingStatesFromDFA();
//TryChangingDFAState();
}
#region Utils component tests
// TEST:Success.
private void TestParameterSplitting() {
// Test alphabet string
string[] alphabetResult = Utils.SplitParameter(_alphabet);
Console.WriteLine("Alphabet: ");
for (int i = 0; i < alphabetResult.Length; i++) {
Console.WriteLine(alphabetResult[i]);
}//for
//Test states string
var statesResult = Utils.SplitParameter(_states);
Console.WriteLine("States: ");
for (int i = 0; i < statesResult.Length; i++)
{
Console.WriteLine(statesResult[i]);
}//for
//Test transitionFunction string
var transitionFunctionResult = Utils.SplitParameter(_transitionFunction);
Console.WriteLine("Transition sets: ");
for (int i = 0; i < transitionFunctionResult.Length; i++)
{
Console.WriteLine(transitionFunctionResult[i]);
}
}
//TEST:Success.
private void TestStateAndTransitionsSplitting() {
var splittingResult = Utils.SplitParameter(_transitionFunction);
for (int i = 0; i < splittingResult.Length; i++) {
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
}//for
}//TestStateAndTransitionsSplitting
//TEST:Success.
private void TestParameterDuplicates() {
var duplicate = "a,a,b,c";
var resultAfterSplit = Utils.SplitParameter(duplicate);
var isDuplicate = Utils.CheckForDuplicates(resultAfterSplit);
}
#endregion
#region Transition Component tests
private Transition _transitionA;
private Transition _transitionB;
//TEST: Success
private void CreateTestTransitions() {
_transitionA = new Transition("a", 0);
_transitionB = new Transition("b", 0);
Console.WriteLine("Transition name: " + _transitionA.TransitionName + " transition ID: " + _transitionA.TransitionID.ToString());
Console.WriteLine("Transition name: " + _transitionB.TransitionName + " transition ID: " + _transitionB.TransitionID.ToString());
}//CreateTestTransitions
//TEST: Success.
private void CreateTestTransitionsFromString() {
var listOfTestTransitions = Utils.CreateTransitionsFromAlphabet(_alphabet);
if(listOfTestTransitions != null){
Console.WriteLine("Number of transitions: " + listOfTestTransitions.Count.ToString());
}//if
}
#endregion
#region State Component Tests
private State _testStateA;
private State _testStateB;
//TEST: Success.
private void CreateTestStates() {
_testStateA = new DefaultState("A", 0);
_testStateB = new DefaultState("B", 0);
Console.WriteLine("State name is: " + _testStateA.StateName + " and ID: " + _testStateA.StateID.ToString());
Console.WriteLine("State name is: " + _testStateB.StateName + " and ID: " + _testStateB.StateID.ToString());
}//CreateTestStates
//TEST: Success
private void CreateTestStatesFromString() {
var listOfTestStates = Utils.CreateDefaultStatesFromString(_states);
if (listOfTestStates != null)
{
Console.WriteLine("Number of states: " + listOfTestStates.Count.ToString());
}//if
}
private List<Transition> _testTransitionsFromString;
private List<State> _testStatesFromString;
//TEST: Success.
private void TryAddingTransitionsToState() {
_testTransitionsFromString = Utils.CreateTransitionsFromAlphabet(_alphabet); //List of transitions
_testStatesFromString = Utils.CreateDefaultStatesFromString(_states); //List of states
var splittingResult = Utils.SplitParameter(_transitionFunction);
for (int i = 0; i < splittingResult.Length; i++)
{
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
foreach(var state in _testStatesFromString){
if(state.StateName.Equals(furtherSplitResult[0])){
Transition tempTransition = null;
foreach (var trans in _testTransitionsFromString) {
if(trans.TransitionName.Equals(furtherSplitResult[1])){
tempTransition = trans;
}//if
}//foreach
State tempState = null;
foreach (var stat in _testStatesFromString) {
if(stat.StateName.Equals(furtherSplitResult[2])){
tempState = stat;
}//if
}//foreach
state.AddTransition(tempTransition, tempState);
Console.WriteLine("Added transition " + tempTransition.TransitionName + " leading to state " + tempState.StateName + " in state " + state.StateName + " transitions.");
}//if
}//foreach
}//for
}//TryAddingTransitionsToState
//TEST: Success.
private void TryRemovingTransitionsFromState() {
TryAddingTransitionsToState();
State state = _testStatesFromString[1];
Console.WriteLine("State name: " + state.StateName);
var testStatesTransitions = state.StateTransitions;
//print state's transitions
foreach (var entry in testStatesTransitions) {
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
state.RemoveTransition(_testTransitionsFromString[1]);
//print state's transitions
foreach (var entry in testStatesTransitions)
{
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
}
//TEST: success
private void TryGettingStateToTransit() {
TryAddingTransitionsToState();
State state = _testStatesFromString[1];
Console.WriteLine("State name: " + state.StateName);
var testStatesTransitions = state.StateTransitions;
//print state's transitions
foreach (var entry in testStatesTransitions)
{
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
Console.WriteLine("Transition name: " + _testTransitionsFromString[1].TransitionName + " transition ID: " + _testTransitionsFromString[1].TransitionID.ToString());
int stateIdToTransit = state.GetStateToTransit(_testTransitionsFromString[1]); //should return 0.
Console.WriteLine("State to transit has id of: " + stateIdToTransit.ToString());
stateIdToTransit = state.GetStateToTransit(_testTransitionsFromString[2]); //should return -1.
Console.WriteLine("State to transit has id of: " + stateIdToTransit.ToString());
}
/*
private void StringSplitTest() {
string alphabet = "a,b,c";
string states = "A,B,C";
string transitions = "{A,a,B};{B,a,C};{B,b,A};{C,c,A}";
string startingState = "A";
string testString ="{A,a,B};{B,a,C};{B,b,A};{C,c,A}"; //Transition string
//string[] sets = testString.Split(';');
string[] delimiters = { "{","}",";"};
string[] sets = testString.Split(delimiters,StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < sets.Length; i++) {
Console.WriteLine(sets[i]);
}
Console.WriteLine(sets.Length.ToString());
//resolve state and transitions
foreach(string sub in sets){
//further split
string[] temp = sub.Split(',');
Console.WriteLine("From state " + temp[0] + " there is a transtion " + temp[1] + " to state " + temp[2]);
}
}
*/
#endregion
#region DFA Component tests
private DFA _dfa;
private void CreateDFA() {
_testTransitionsFromString = Utils.CreateTransitionsFromAlphabet(_alphabet);
_testStatesFromString = Utils.CreateDefaultStatesFromString(_states);
TryAddingTransitionsToState();
_dfa = new DFA(_testTransitionsFromString, _testStatesFromString);
Console.WriteLine("Created DFA!");
}//CreateDFA
private List<State> _listOfStatesInDFA;
//TEST:Success.
private void TryAddingStatesToDFA() {
CreateDFA();
_listOfStatesInDFA = _dfa.States;
Console.WriteLine("DFA has following states: ");
foreach (State state in _listOfStatesInDFA) {
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
_dfa.AddState(new DefaultState("A", 0)); //should fail because of same id and name.
_dfa.AddState(new DefaultState("D", 3)); //should succeed.
_dfa.AddState(new DefaultState("A", 4)); //should fail because of same name.
Console.WriteLine("DFA has following states after adding: ");
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
Console.WriteLine("Done adding states to dfa");
}
//TEST: Success.
private void TryRemovingStatesFromDFA() {
CreateDFA();
TryAddingStatesToDFA();
_dfa.CurrentState = _listOfStatesInDFA[0];
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
_dfa.RemoveState(_listOfStatesInDFA[2]); //should succeed.
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
State failTestState = new DefaultState("B", 2); //should fail.
_dfa.RemoveState(failTestState);
Console.WriteLine("Done removing states from DFA");
}
//TEST: Succes.
private void TryChangingDFAState() {
//Create DFA with states and transitions
CreateDFA();
TryAddingStatesToDFA();
//assign one of the states active
_dfa.CurrentState = _listOfStatesInDFA[0];
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
//perform transition
_dfa.PerformTransition(_testTransitionsFromString[0]); //should succeed.
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
_dfa.PerformTransition(_testTransitionsFromString[2]); //should fail
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
}
#endregion
}//Tests
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace harjoitustyo
{
class Tests
{
// Test variables;
private string _alphabet = "a,b,c"; //names of the transitions
private string _states = "A,B,C"; //names of the states
private string _transitionFunction = "{A-a-B};{B-a-C};{B-b-A};{C-c-A}"; //Transition functions: for example {A,a,B} means State A has a transition a to state B.
private string _startingState = "A";
/// <summary>
/// Drives a set of tests.
/// </summary>
public void DriveTests() {
//Utils component tests
//TestParameterSplitting();
//TestStateAndTransitionsSplitting();
//TestParameterDuplicates();
//Transition component tests
//CreateTestTransitions();
//CreateTestTransitionsFromString();
//State component tests
//CreateTestStates();
//CreateTestStatesFromString();
//TryAddingTransitionsToState();
//TryRemovingTransitionsFromState();
//TryGettingStateToTransit();
//DFA component tests
//CreateDFA();
//TryAddingStatesToDFA();
//TryRemovingStatesFromDFA();
//TryChangingDFAState();
}
#region Utils component tests
// TEST:Success.
private void TestParameterSplitting() {
// Test alphabet string
string[] alphabetResult = Utils.SplitParameter(_alphabet);
Console.WriteLine("Alphabet: ");
for (int i = 0; i < alphabetResult.Length; i++) {
Console.WriteLine(alphabetResult[i]);
}//for
//Test states string
var statesResult = Utils.SplitParameter(_states);
Console.WriteLine("States: ");
for (int i = 0; i < statesResult.Length; i++)
{
Console.WriteLine(statesResult[i]);
}//for
//Test transitionFunction string
var transitionFunctionResult = Utils.SplitParameter(_transitionFunction);
Console.WriteLine("Transition sets: ");
for (int i = 0; i < transitionFunctionResult.Length; i++)
{
Console.WriteLine(transitionFunctionResult[i]);
}
}
//TEST:Success.
private void TestStateAndTransitionsSplitting() {
var splittingResult = Utils.SplitParameter(_transitionFunction);
for (int i = 0; i < splittingResult.Length; i++) {
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
}//for
}//TestStateAndTransitionsSplitting
//TEST:Success.
private void TestParameterDuplicates() {
var duplicate = "a,a,b,c";
var resultAfterSplit = Utils.SplitParameter(duplicate);
var isDuplicate = Utils.CheckForDuplicates(resultAfterSplit);
}
#endregion
#region Transition Component tests
private Transition _transitionA;
private Transition _transitionB;
//TEST: Success
private void CreateTestTransitions() {
_transitionA = new Transition("a", 0);
_transitionB = new Transition("b", 0);
Console.WriteLine("Transition name: " + _transitionA.TransitionName + " transition ID: " + _transitionA.TransitionID.ToString());
Console.WriteLine("Transition name: " + _transitionB.TransitionName + " transition ID: " + _transitionB.TransitionID.ToString());
}//CreateTestTransitions
//TEST: Success.
private void CreateTestTransitionsFromString() {
var listOfTestTransitions = Utils.CreateTransitionsFromAlphabet(_alphabet);
if(listOfTestTransitions != null){
Console.WriteLine("Number of transitions: " + listOfTestTransitions.Count.ToString());
}//if
}
#endregion
#region State Component Tests
private State _testStateA;
private State _testStateB;
//TEST: Success.
private void CreateTestStates() {
_testStateA = new DefaultState("A", 0);
_testStateB = new DefaultState("B", 0);
Console.WriteLine("State name is: " + _testStateA.StateName + " and ID: " + _testStateA.StateID.ToString());
Console.WriteLine("State name is: " + _testStateB.StateName + " and ID: " + _testStateB.StateID.ToString());
}//CreateTestStates
//TEST: Success
private void CreateTestStatesFromString() {
var listOfTestStates = Utils.CreateDefaultStatesFromString(_states);
if (listOfTestStates != null)
{
Console.WriteLine("Number of states: " + listOfTestStates.Count.ToString());
}//if
}
private List<Transition> _testTransitionsFromString;
private List<State> _testStatesFromString;
//TEST: Success.
private void TryAddingTransitionsToState() {
_testTransitionsFromString = Utils.CreateTransitionsFromAlphabet(_alphabet); //List of transitions
_testStatesFromString = Utils.CreateDefaultStatesFromString(_states); //List of states
var splittingResult = Utils.SplitParameter(_transitionFunction);
for (int i = 0; i < splittingResult.Length; i++)
{
var furtherSplitResult = Utils.SplitStateTransitions(splittingResult[i]);
Console.WriteLine("From state " + furtherSplitResult[0] + " there is transition " + furtherSplitResult[1] + " to state " + furtherSplitResult[2]);
foreach(var state in _testStatesFromString){
if(state.StateName.Equals(furtherSplitResult[0])){
Transition tempTransition = null;
foreach (var trans in _testTransitionsFromString) {
if(trans.TransitionName.Equals(furtherSplitResult[1])){
tempTransition = trans;
}//if
}//foreach
State tempState = null;
foreach (var stat in _testStatesFromString) {
if(stat.StateName.Equals(furtherSplitResult[2])){
tempState = stat;
}//if
}//foreach
state.AddTransition(tempTransition, tempState);
Console.WriteLine("Added transition " + tempTransition.TransitionName + " leading to state " + tempState.StateName + " in state " + state.StateName + " transitions.");
}//if
}//foreach
}//for
}//TryAddingTransitionsToState
//TEST: Success.
private void TryRemovingTransitionsFromState() {
TryAddingTransitionsToState();
State state = _testStatesFromString[1];
Console.WriteLine("State name: " + state.StateName);
var testStatesTransitions = state.StateTransitions;
//print state's transitions
foreach (var entry in testStatesTransitions) {
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
state.RemoveTransition(_testTransitionsFromString[1]);
//print state's transitions
foreach (var entry in testStatesTransitions)
{
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
}
//TEST: success
private void TryGettingStateToTransit() {
TryAddingTransitionsToState();
State state = _testStatesFromString[1];
Console.WriteLine("State name: " + state.StateName);
var testStatesTransitions = state.StateTransitions;
//print state's transitions
foreach (var entry in testStatesTransitions)
{
Console.WriteLine("Transition ID: " + entry.Key.ToString() + " State ID: " + entry.Value.ToString());
}
Console.WriteLine("Transition name: " + _testTransitionsFromString[1].TransitionName + " transition ID: " + _testTransitionsFromString[1].TransitionID.ToString());
int stateIdToTransit = state.GetStateToTransit(_testTransitionsFromString[1]); //should return 0.
Console.WriteLine("State to transit has id of: " + stateIdToTransit.ToString());
stateIdToTransit = state.GetStateToTransit(_testTransitionsFromString[2]); //should return -1.
Console.WriteLine("State to transit has id of: " + stateIdToTransit.ToString());
}
/*
private void StringSplitTest() {
string alphabet = "a,b,c";
string states = "A,B,C";
string transitions = "{A,a,B};{B,a,C};{B,b,A};{C,c,A}";
string startingState = "A";
string testString ="{A,a,B};{B,a,C};{B,b,A};{C,c,A}"; //Transition string
//string[] sets = testString.Split(';');
string[] delimiters = { "{","}",";"};
string[] sets = testString.Split(delimiters,StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < sets.Length; i++) {
Console.WriteLine(sets[i]);
}
Console.WriteLine(sets.Length.ToString());
//resolve state and transitions
foreach(string sub in sets){
//further split
string[] temp = sub.Split(',');
Console.WriteLine("From state " + temp[0] + " there is a transtion " + temp[1] + " to state " + temp[2]);
}
}
*/
#endregion
#region DFA Component tests
private DFA _dfa;
private void CreateDFA() {
_testTransitionsFromString = Utils.CreateTransitionsFromAlphabet(_alphabet);
_testStatesFromString = Utils.CreateDefaultStatesFromString(_states);
TryAddingTransitionsToState();
_dfa = new DFA(_testTransitionsFromString, _testStatesFromString);
Console.WriteLine("Created DFA!");
}//CreateDFA
private List<State> _listOfStatesInDFA;
//TEST:Success.
private void TryAddingStatesToDFA() {
CreateDFA();
_listOfStatesInDFA = _dfa.States;
Console.WriteLine("DFA has following states: ");
foreach (State state in _listOfStatesInDFA) {
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
_dfa.AddState(new DefaultState("A", 0)); //should fail because of same id and name.
_dfa.AddState(new DefaultState("D", 3)); //should succeed.
_dfa.AddState(new DefaultState("A", 4)); //should fail because of same name.
Console.WriteLine("DFA has following states after adding: ");
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
Console.WriteLine("Done adding states to dfa");
}
//TEST: Success.
private void TryRemovingStatesFromDFA() {
CreateDFA();
TryAddingStatesToDFA();
_dfa.CurrentState = _listOfStatesInDFA[0];
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
_dfa.RemoveState(_listOfStatesInDFA[2]); //should succeed.
foreach (State state in _listOfStatesInDFA)
{
Console.WriteLine(state.StateID.ToString() + " " + state.StateName);
}//foreach
State failTestState = new DefaultState("B", 2); //should fail.
_dfa.RemoveState(failTestState);
Console.WriteLine("Done removing states from DFA");
}
//TEST: Succes.
private void TryChangingDFAState() {
//Create DFA with states and transitions
CreateDFA();
TryAddingStatesToDFA();
//assign one of the states active
_dfa.CurrentState = _listOfStatesInDFA[0];
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
//perform transition
_dfa.PerformTransition(_testTransitionsFromString[0]); //should succeed.
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
_dfa.PerformTransition(_testTransitionsFromString[2]); //should fail
Console.WriteLine("Currently active state: " + _dfa.CurrentState.StateName);
}
#endregion
}//Tests
}
Transition
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public class Transition
{
// Class variables
private string _transitionName;
public string TransitionName { get { return _transitionName; } }
private int _transitionID;
public int TransitionID { get { return _transitionID; } }
/// <summary>
/// Assigns given parameters to variables.
/// </summary>
/// <param name="transitionName"></param>
/// <param name="transitionID"></param>
public Transition(string transitionName, int transitionID)
{
_transitionName = transitionName;
_transitionID = transitionID;
}//Transition
}//Transition
}
© 2017 GitHub, Inc.
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public class Transition
{
// Class variables
private string _transitionName;
public string TransitionName { get { return _transitionName; } }
private int _transitionID;
public int TransitionID { get { return _transitionID; } }
/// <summary>
/// Assigns given parameters to variables.
/// </summary>
/// <param name="transitionName"></param>
/// <param name="transitionID"></param>
public Transition(string transitionName, int transitionID)
{
_transitionName = transitionName;
_transitionID = transitionID;
}//Transition
}//Transition
}
© 2017 GitHub, Inc.
DFA
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public class DFA
{
private List<State> _states;
public List<State> States { get { return _states; } }
private List<Transition> _alphabet;
public List<Transition> Alphabet { get { return _alphabet; } }
private State _currentState;
public State CurrentState { get { return _currentState; } set { _currentState = value; } }
public DFA(List<Transition> alphabet, List<State>states) {
this._states = states;
this._alphabet = alphabet;
}//Constructor
/// <summary>
/// Adds the given state to dfa.
/// </summary>
/// <param name="stateToAdd"></param>
public void AddState(State stateToAdd) {
//Check whether given state already exists in DFA or the given state has same ID or name as some other state in DFA
foreach (State existingState in _states) {
if(existingState.StateID == stateToAdd.StateID){
Console.WriteLine("ERROR: Cannot add state to the dfa with same id!");
return;
}//if
if (existingState.StateName.Equals(stateToAdd.StateName))
{
Console.WriteLine("ERROR: Cannot add state to the dfa with same name!");
return;
}//if
}//foreach
// Add the state
_states.Add(stateToAdd);
}//AddState
/// <summary>
/// Removes the given state from dfa.
/// </summary>
/// <param name="StateToRemove"></param>
public void RemoveState(State StateToRemove) {
// Check whether the state to be removed is current state. Removing current state is not allowed.
if(StateToRemove.StateID == _currentState.StateID){
Console.WriteLine("ERROR: Cannot remove state that is currently active.");
return;
}//if
// Loops through dfa's states and compares their id to given state's id. If match is found, state is removed from dfa.
foreach(State existingState in _states){
if(existingState.StateID == StateToRemove.StateID){
_states.Remove(StateToRemove);
Console.WriteLine("Removed state " + StateToRemove.StateName + " with an id of " + StateToRemove.StateID.ToString() + " from dfa.");
return;
}//if
}//foreach
//If state was not found, print error
Console.WriteLine("ERROR: state " + StateToRemove.StateName + " with an id of " + StateToRemove.StateID.ToString() + " was not found in dfa.");
}//RemoveState
/// <summary>
/// Performs a transition to a new state.
/// </summary>
/// <param name="transition"></param>
public void PerformTransition(Transition transition) {
// Check the state's transitions and get the id of the state where to transit. If state doesn't have transition, it returns -1, which means looping back to itself
int statetoTransit = _currentState.GetStateToTransit(transition);
if(statetoTransit != -1){
foreach(State newState in _states){
if (newState.StateID == statetoTransit) {
// Before transiting to new state, let the old state finish up and the new one to initialize.
_currentState.onLeavingState();
_currentState = newState;
_currentState.onEnteringState();
}//if
}//foreach
}//if
}//PerformTransition
public void PerformTransition(string transitionName) {
//Check Whether transition exists
foreach(Transition transition in _alphabet){
if(transition.TransitionName.Equals(transitionName)){
PerformTransition(transition);
}//if
}//foreach
}//PerformTransition
}//DFA
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace harjoitustyo
{
public class DFA
{
private List<State> _states;
public List<State> States { get { return _states; } }
private List<Transition> _alphabet;
public List<Transition> Alphabet { get { return _alphabet; } }
private State _currentState;
public State CurrentState { get { return _currentState; } set { _currentState = value; } }
public DFA(List<Transition> alphabet, List<State>states) {
this._states = states;
this._alphabet = alphabet;
}//Constructor
/// <summary>
/// Adds the given state to dfa.
/// </summary>
/// <param name="stateToAdd"></param>
public void AddState(State stateToAdd) {
//Check whether given state already exists in DFA or the given state has same ID or name as some other state in DFA
foreach (State existingState in _states) {
if(existingState.StateID == stateToAdd.StateID){
Console.WriteLine("ERROR: Cannot add state to the dfa with same id!");
return;
}//if
if (existingState.StateName.Equals(stateToAdd.StateName))
{
Console.WriteLine("ERROR: Cannot add state to the dfa with same name!");
return;
}//if
}//foreach
// Add the state
_states.Add(stateToAdd);
}//AddState
/// <summary>
/// Removes the given state from dfa.
/// </summary>
/// <param name="StateToRemove"></param>
public void RemoveState(State StateToRemove) {
// Check whether the state to be removed is current state. Removing current state is not allowed.
if(StateToRemove.StateID == _currentState.StateID){
Console.WriteLine("ERROR: Cannot remove state that is currently active.");
return;
}//if
// Loops through dfa's states and compares their id to given state's id. If match is found, state is removed from dfa.
foreach(State existingState in _states){
if(existingState.StateID == StateToRemove.StateID){
_states.Remove(StateToRemove);
Console.WriteLine("Removed state " + StateToRemove.StateName + " with an id of " + StateToRemove.StateID.ToString() + " from dfa.");
return;
}//if
}//foreach
//If state was not found, print error
Console.WriteLine("ERROR: state " + StateToRemove.StateName + " with an id of " + StateToRemove.StateID.ToString() + " was not found in dfa.");
}//RemoveState
/// <summary>
/// Performs a transition to a new state.
/// </summary>
/// <param name="transition"></param>
public void PerformTransition(Transition transition) {
// Check the state's transitions and get the id of the state where to transit. If state doesn't have transition, it returns -1, which means looping back to itself
int statetoTransit = _currentState.GetStateToTransit(transition);
if(statetoTransit != -1){
foreach(State newState in _states){
if (newState.StateID == statetoTransit) {
// Before transiting to new state, let the old state finish up and the new one to initialize.
_currentState.onLeavingState();
_currentState = newState;
_currentState.onEnteringState();
}//if
}//foreach
}//if
}//PerformTransition
public void PerformTransition(string transitionName) {
//Check Whether transition exists
foreach(Transition transition in _alphabet){
if(transition.TransitionName.Equals(transitionName)){
PerformTransition(transition);
}//if
}//foreach
}//PerformTransition
}//DFA
}
Turing Machine Simulation in C#
using System;
using System.Collections.Generic;
using System.Linq;
namespace TuringMachine
{
public class Head
{
public const char Blank = '_';
public Head(IEnumerable<char> tape, int headPosition)
{
if (tape == null) throw new ArgumentNullException(nameof(tape));
var safeData = tape as char[] ?? tape.ToArray();
if (headPosition > safeData.Count() - 1 || headPosition < 0)
throw new IndexOutOfRangeException("Invalid head position");
Tape = safeData;
HeadPosition = headPosition;
}
public IEnumerable<char> Tape { get; }
public int HeadPosition { get; }
public Head Write(char head) =>
new Head(new List<char>(Tape) { [HeadPosition] = head }, HeadPosition);
public Head MoveLeft() => HeadPosition == 0
? new Head(new[] { Blank }.Concat(Tape), 0)
: new Head(Tape, HeadPosition - 1);
public Head MoveRight() => HeadPosition == Tape.Count() - 1
? new Head(Tape.Concat(new[] { Blank }), HeadPosition + 1)
: new Head(Tape, HeadPosition + 1);
public Head Move(HeadDirection direction)
{
switch (direction)
{
case HeadDirection.Left:
return MoveLeft();
case HeadDirection.NoMove:
return this;
case HeadDirection.Right:
return MoveRight();
default:
throw new ArgumentOutOfRangeException(nameof(direction), direction, null);
}
}
public char Read() => Tape.ElementAt(HeadPosition);
public override string ToString() => $@"Tape:
{Tape.Select(GetChar).Aggregate((agg, next) => agg + next)}";
private string GetChar(char c, int index) =>
index == HeadPosition ? $"({c})" : c.ToString();
}
}
namespace TuringMachine
{
public class Transition
{
public Transition(int initialState, char read, char write, HeadDirection headDirection, int nextState)
{
InitialState = initialState;
Read = read;
Write = write;
HeadDirection = headDirection;
NextState = nextState;
}
public int InitialState { get; }
public char Read { get; }
public char Write { get; }
public HeadDirection HeadDirection { get; }
public int NextState { get; }
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace TuringMachine
{
public class Machine
{
public Machine(int state, Head head, IEnumerable<transition> transitionTable)
{
if (head == null) throw new ArgumentNullException(nameof(head));
if (transitionTable == null) throw new ArgumentNullException(nameof(transitionTable));
State = state;
Head = head;
TransitionTable = transitionTable;
}
public int State { get; }
public Head Head { get; }
public IEnumerable<transition> TransitionTable { get; }
public Machine Step()
{
if (State < 0) return this;
return
TransitionTable
.Where(t => t.InitialState == State && t.Read == Head.Read())
.DefaultIfEmpty(new Transition(0, Head.Blank, Head.Read(), HeadDirection.NoMove,
TuringMachine.State.Error))
.Select(
t => new Machine(t.NextState, Head.Write(t.Write).Move(t.HeadDirection), TransitionTable))
.First();
}
public Machine Run()
{
var m = this;
while (m.State >= 0)
m = m.Step();
return m;
}
}
}
using System.Collections.Generic;
using System.Resources;
namespace TuringMachine
{
public static class TransitionTableGenerator
{
public static IEnumerable<transition> Addition() => new[]
{
new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
new Transition(0, '1', '1', HeadDirection.Right, 1),
new Transition(1, Tape.Blank, '1', HeadDirection.Right, 2),
new Transition(1, '1', '1', HeadDirection.Right, 1),
new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
new Transition(2, '1', '1', HeadDirection.Right, 2),
new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
new Transition(3, '1', Tape.Blank, HeadDirection.Left, 4),
new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(4, '1', '1', HeadDirection.Left, 4)
};
}
}
using System.Collections.Generic;
using System.Resources;
namespace TuringMachine
{
public static class TransitionTableGenerator
{
public static IEnumerable<transition> Multiplication() => new[]
{
new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 1),
new Transition(0, '1', Tape.Blank, HeadDirection.Right, 2),
new Transition(1, Tape.Blank, Tape.Blank, HeadDirection.Right, 14),
new Transition(1, '1', Tape.Blank, HeadDirection.Right, 2),
new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Right, 3),
new Transition(2, '1', '1', HeadDirection.Right, 2),
new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 15),
new Transition(3, '1', Tape.Blank, HeadDirection.Right, 4),
new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.Right, 5),
new Transition(4, '1', '1', HeadDirection.Right, 4),
new Transition(5, Tape.Blank, '1', HeadDirection.Left, 6),
new Transition(5, '1', '1', HeadDirection.Right, 5),
new Transition(6, Tape.Blank, Tape.Blank, HeadDirection.Left, 7),
new Transition(6, '1', '1', HeadDirection.Left, 6),
new Transition(7, Tape.Blank, '1', HeadDirection.Left, 9),
new Transition(7, '1', '1', HeadDirection.Left, 8),
new Transition(8, Tape.Blank, '1', HeadDirection.Right, 3),
new Transition(8, '1', '1', HeadDirection.Left, 8),
new Transition(9, Tape.Blank, Tape.Blank, HeadDirection.Left, 10),
new Transition(9, '1', '1', HeadDirection.Left, 9),
new Transition(10, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
new Transition(10, '1', '1', HeadDirection.Left, 11),
new Transition(11, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
new Transition(11, '1', '1', HeadDirection.Left, 11),
new Transition(12, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
new Transition(12, '1', Tape.Blank, HeadDirection.Right, 13),
new Transition(13, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(13, '1', Tape.Blank, HeadDirection.Right, 13),
new Transition(14, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(14, '1', Tape.Blank, HeadDirection.Right, 14),
new Transition(15, Tape.Blank, Tape.Blank, HeadDirection.Left, 16),
new Transition(15, '1', Tape.Blank, HeadDirection.Left, 15),
new Transition(16, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(16, '1', Tape.Blank, HeadDirection.Left, 16)
};
}
}
using System.Collections.Generic;
using System.Linq;
namespace TuringMachine
{
public class Head
{
public const char Blank = '_';
public Head(IEnumerable<char> tape, int headPosition)
{
if (tape == null) throw new ArgumentNullException(nameof(tape));
var safeData = tape as char[] ?? tape.ToArray();
if (headPosition > safeData.Count() - 1 || headPosition < 0)
throw new IndexOutOfRangeException("Invalid head position");
Tape = safeData;
HeadPosition = headPosition;
}
public IEnumerable<char> Tape { get; }
public int HeadPosition { get; }
public Head Write(char head) =>
new Head(new List<char>(Tape) { [HeadPosition] = head }, HeadPosition);
public Head MoveLeft() => HeadPosition == 0
? new Head(new[] { Blank }.Concat(Tape), 0)
: new Head(Tape, HeadPosition - 1);
public Head MoveRight() => HeadPosition == Tape.Count() - 1
? new Head(Tape.Concat(new[] { Blank }), HeadPosition + 1)
: new Head(Tape, HeadPosition + 1);
public Head Move(HeadDirection direction)
{
switch (direction)
{
case HeadDirection.Left:
return MoveLeft();
case HeadDirection.NoMove:
return this;
case HeadDirection.Right:
return MoveRight();
default:
throw new ArgumentOutOfRangeException(nameof(direction), direction, null);
}
}
public char Read() => Tape.ElementAt(HeadPosition);
public override string ToString() => $@"Tape:
{Tape.Select(GetChar).Aggregate((agg, next) => agg + next)}";
private string GetChar(char c, int index) =>
index == HeadPosition ? $"({c})" : c.ToString();
}
}
namespace TuringMachine
{
public class Transition
{
public Transition(int initialState, char read, char write, HeadDirection headDirection, int nextState)
{
InitialState = initialState;
Read = read;
Write = write;
HeadDirection = headDirection;
NextState = nextState;
}
public int InitialState { get; }
public char Read { get; }
public char Write { get; }
public HeadDirection HeadDirection { get; }
public int NextState { get; }
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace TuringMachine
{
public class Machine
{
public Machine(int state, Head head, IEnumerable<transition> transitionTable)
{
if (head == null) throw new ArgumentNullException(nameof(head));
if (transitionTable == null) throw new ArgumentNullException(nameof(transitionTable));
State = state;
Head = head;
TransitionTable = transitionTable;
}
public int State { get; }
public Head Head { get; }
public IEnumerable<transition> TransitionTable { get; }
public Machine Step()
{
if (State < 0) return this;
return
TransitionTable
.Where(t => t.InitialState == State && t.Read == Head.Read())
.DefaultIfEmpty(new Transition(0, Head.Blank, Head.Read(), HeadDirection.NoMove,
TuringMachine.State.Error))
.Select(
t => new Machine(t.NextState, Head.Write(t.Write).Move(t.HeadDirection), TransitionTable))
.First();
}
public Machine Run()
{
var m = this;
while (m.State >= 0)
m = m.Step();
return m;
}
}
}
using System.Collections.Generic;
using System.Resources;
namespace TuringMachine
{
public static class TransitionTableGenerator
{
public static IEnumerable<transition> Addition() => new[]
{
new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
new Transition(0, '1', '1', HeadDirection.Right, 1),
new Transition(1, Tape.Blank, '1', HeadDirection.Right, 2),
new Transition(1, '1', '1', HeadDirection.Right, 1),
new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
new Transition(2, '1', '1', HeadDirection.Right, 2),
new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
new Transition(3, '1', Tape.Blank, HeadDirection.Left, 4),
new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(4, '1', '1', HeadDirection.Left, 4)
};
}
}
using System.Collections.Generic;
using System.Resources;
namespace TuringMachine
{
public static class TransitionTableGenerator
{
public static IEnumerable<transition> Multiplication() => new[]
{
new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 1),
new Transition(0, '1', Tape.Blank, HeadDirection.Right, 2),
new Transition(1, Tape.Blank, Tape.Blank, HeadDirection.Right, 14),
new Transition(1, '1', Tape.Blank, HeadDirection.Right, 2),
new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Right, 3),
new Transition(2, '1', '1', HeadDirection.Right, 2),
new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 15),
new Transition(3, '1', Tape.Blank, HeadDirection.Right, 4),
new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.Right, 5),
new Transition(4, '1', '1', HeadDirection.Right, 4),
new Transition(5, Tape.Blank, '1', HeadDirection.Left, 6),
new Transition(5, '1', '1', HeadDirection.Right, 5),
new Transition(6, Tape.Blank, Tape.Blank, HeadDirection.Left, 7),
new Transition(6, '1', '1', HeadDirection.Left, 6),
new Transition(7, Tape.Blank, '1', HeadDirection.Left, 9),
new Transition(7, '1', '1', HeadDirection.Left, 8),
new Transition(8, Tape.Blank, '1', HeadDirection.Right, 3),
new Transition(8, '1', '1', HeadDirection.Left, 8),
new Transition(9, Tape.Blank, Tape.Blank, HeadDirection.Left, 10),
new Transition(9, '1', '1', HeadDirection.Left, 9),
new Transition(10, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
new Transition(10, '1', '1', HeadDirection.Left, 11),
new Transition(11, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
new Transition(11, '1', '1', HeadDirection.Left, 11),
new Transition(12, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
new Transition(12, '1', Tape.Blank, HeadDirection.Right, 13),
new Transition(13, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(13, '1', Tape.Blank, HeadDirection.Right, 13),
new Transition(14, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(14, '1', Tape.Blank, HeadDirection.Right, 14),
new Transition(15, Tape.Blank, Tape.Blank, HeadDirection.Left, 16),
new Transition(15, '1', Tape.Blank, HeadDirection.Left, 15),
new Transition(16, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
new Transition(16, '1', Tape.Blank, HeadDirection.Left, 16)
};
}
}
Subscribe to:
Posts (Atom)