Hello. I am doing a simple project which consists of 3 questions. It is related to finite automata. In the second question, we have to convert an NFA to DFA, but we must not simplify the result DFA.
My implementation can only pass half of the test cases. I have 3
class in my code.
The first one is for every state in the automata, here is its code:
public class State
{
public bool isFinal;
public bool isInitial;
public string name;
public List<Transition> transitions = new List<Transition>();
public State(){}
public State(bool _isFinal, bool _isInitial, string _name)
{
isFinal = _isFinal;
isInitial = _isInitial;
name = _name;
}
}
And another class for storing information about every transition:
public class Transition
{
public State start {get; set;}
public State end {get; set;}
public char symbol {get; set;}
}
The final
class consists of 2 methods.
public class NFAtoDFA
{
public List<State> states {get; set;}
public List<Transition> transitions {get; set;}
public List<char> symbols {get; set;}
public NFAtoDFA(List<State> _states, List<Transition> _transitions,
List<char> _symbols)
{
states = _states;
transitions = _transitions;
symbols = _symbols;
}
public int convertNFAtoDFA()
{
List<State> newStates = new List<State>();
for (int i = 0; i < states.Count; i++)
{
State tmpState = new State();
tmpState.isFinal = states[i].isFinal;
tmpState.isInitial = states[i].isInitial;
for (int j = 0; j < states[i].transitions.Count; j++)
{
Transition tmpTr = new Transition();
tmpTr.start = states[i].transitions[j].start;
tmpTr.end = states[i].transitions[j].end;
tmpTr.symbol = states[i].transitions[j].symbol;
tmpState.transitions.Add(tmpTr);
}
tmpState.name = states[i].name;
newStates.Add(tmpState);
}
for (int i = 0; i < states.Count; i++)
{
for (int j = 0; j < states[i].transitions.Count; j++)
{
if (states[i].transitions[j].symbol == '$')
{
states[i].name = states[i].name + " " +
states[i].transitions[j].end.name;
}
}
states[i].name = states[i].name.Trim();
}
for (int i = states.Count - 1; i >= 0; i--)
{
for (int j = states[i].transitions.Count - 1; j >= 0; j--)
{
if (states[i].transitions[j].symbol == '$')
{
states[i].transitions.Remove(states[i].transitions[j]);
}
}
}
List<State> DFA = new List<State>();
State Initial = new State(states[0].isFinal, true, states[0].name);
DFA.Add(Initial);
for (int i = 0; i < DFA.Count; i++)
{
for (int j = 0; j < symbols.Count; j++)
{
State tmp = new State();
tmp.isFinal = false;
List<State> newAdjStates = new List<State>();
var statesName = DFA[i].name.Trim().Split(' ');
for (int k = 0; k < statesName.Length; k++)
{
for (int m = 0; m < newStates.Count; m++)
{
for (int n = 0; n < newStates[m].transitions.Count; n++)
{
if (newStates[m].name == statesName[k]
&&
(char)newStates[m].transitions[n].symbol == symbols[j])
{
newAdjStates.Add(newStates[m].transitions[n].end);
}
}
}
}
string newName = "";
for (int k = 0; k < newAdjStates.Count; k++)
{
newName = newName + " " + newAdjStates[k].name;
}
for (int k = 0; k < newAdjStates.Count; k++)
{
if (newAdjStates[k].isFinal)
{
tmp.isFinal = true;
}
}
tmp.name = newName;
bool exist = false;
int index = -1;
for (int k = 0; k <= i; k++)
{
if (DFA[k].name.Trim() == newName.Trim())
{
exist = true;
index = k;
}
}
Transition trDFA = new Transition();
if (exist)
{
trDFA.start = DFA[i];
trDFA.symbol = symbols[j];
trDFA.end = DFA[index];
DFA[i].transitions.Add(trDFA);
}
else
{
trDFA.start = DFA[i];
trDFA.symbol = symbols[j];
trDFA.end = tmp;
DFA.Add(tmp);
DFA[i].transitions.Add(trDFA);
}
}
}
return removeDuplicates(DFA);
}
public int removeDuplicates(List<State> DFA)
{
Dictionary<string, List<string>> resDFA =
new Dictionary<string, List<string>>();
StringBuilder sb;
for (int i = 0; i < DFA.Count; i++)
{
for (int j = 0; j < DFA[i].transitions.Count; j++)
{
sb = new StringBuilder();
string source = DFA[i].transitions[j].start.name.Trim();
string dest = DFA[i].transitions[j].end.name.Trim();
char symbol = DFA[i].transitions[j].symbol;
if (source == "" || source == null)
{
source = "Trap";
}
if (dest == "" || dest == null)
{
dest = "Trap";
}
sb.Append($"{source} + {symbol} + {dest}");
if (resDFA.ContainsKey(source.Trim()))
{
List<string> list = resDFA[source];
if (!list.Contains(sb.ToString()) && sb.ToString() != "")
{
list.Add(sb.ToString());
}
}
else
{
List<string> list = new List<string>();
list.Add(sb.ToString());
resDFA.Add(source.Trim(), list);
}
}
}
return resDFA.Keys.Count;
}
}
And here is the driver code:
class Program
{
static void Main(string[] args)
{
List<State> NFA = new List<State>();
List<Transition> transitions = new List<Transition>();
var states = Console.ReadLine().Split(',', '{', '}').
Where(x => !string.IsNullOrWhiteSpace(x)).ToList();
var sigma = Console.ReadLine().Split(',', '{', '}').
Where(x => !string.IsNullOrWhiteSpace(x)).
Select(item => char.Parse(item)).ToList();
var finals = Console.ReadLine().Split(',', '{', '}').
Where(x => !string.IsNullOrWhiteSpace(x)).ToList();
long numberOfTransitions = Convert.ToInt64(Console.ReadLine());
for (int i = 0; i < states.Count; i++)
{
State newState = new State();
if (i == 0)
{
newState.isInitial = true;
}
newState.name = states[i];
NFA.Add(newState);
}
for (int i = 0; i < finals.Count; i++)
{
for (int j = 0; j < NFA.Count; j++)
{
if (NFA[j].name == finals[i])
{
NFA[j].isFinal = true;
}
}
}
for (int i = 0; i < numberOfTransitions; i++)
{
var t = Console.ReadLine().Split(',');
Transition tr = new Transition();
tr.symbol = Convert.ToChar(t[1]);
for (int j = 0; j < NFA.Count; j++)
{
if (NFA[j].name == t[0])
{
tr.start = NFA[j];
}
if (NFA[j].name == t[2])
{
tr.end = NFA[j];
}
}
transitions.Add(tr);
}
for (int i = 0; i < NFA.Count; i++)
{
for (int j = 0; j < transitions.Count; j++)
{
if (NFA[i] == transitions[j].start)
{
NFA[i].transitions.Add(transitions[j]);
}
}
}
NFAtoDFA obj = new NFAtoDFA(NFA, transitions, sigma);
System.Console.WriteLine(obj.convertNFAtoDFA());
}
}
For example for the below test case, my test does not work correctly(The output should be 11, but for me is 3).
{q0,q1,q2,q3,q4,q5,q6}
{0,1}
{q6}
11
q0,0,q1
q0,1,q1
q1,1,q1
q2,0,q3
q3,$,q1
q3,1,q4
q4,0,q5
q5,1,q3
q5,1,q6
q6,0,q6
q6,1,q6
What I have tried:
I know that it is hard to answer this kind of question, and I have to rectify the algorithm on my own, but I will be grateful for any help or advice.
Submit an article or tip