DFA化简步骤

1.   将DFA状态集分为结束状态集F和非结束状态集S。F为DFA结束状态，S为结束状态以外的所有其它DFA状态。F和S构成状态集G；
2.   对G的每个子集T，对子集T的每个状态S执行move(S, a)得到状态，找到状态所属G的子集，根据将子集T划分为n个子集；
3.   重复2直到不能再划分子集；
4.   对G中状态个数大于一的子集T，只保留一个状态，去掉T多余的状态。

private NFAToDFA dfa;public IEnumerable<int[]> DFA2MFA()
{var states = new List<int[]>();//dfa结束状态集和非结束状态集var allStates = Enumerable.Range(0, dfa.DFA.GetLength(0)).ToArray();var acceptStates = dfa.FinalStates;var nonAcceptStates = (from state in allStateswhere !acceptStates.Contains(state)select state).ToArray();states.Add(nonAcceptStates);states.Add(acceptStates);var compared = new List<int[]>(states);while (true){foreach(var item in states){if (item.Length < 2) continue;for (var i = 0; i < Transitions.Length; ++i){var groups = (from state in itemgroup state by states.FindIndex(array => array.Contains(dfa.DFA[state, i])) into gselect g).ToArray();if (groups.Length < 2) continue;var removeds = (from array in groupsfrom removed in arrayselect removed).ToArray();compared.RemoveAll(array => array.Any(state => removed.Contains(state)));foreach(var group in groups)compared.Add(group.ToArray());}}if (Equal(states, compared)) break;states.Clear();states.AddRange(compared);}return states;
}

MFA 代码

public class DFAToMFA
{public int[,] MFA { get; private set; }public int InitialState { get; private set; }public int[] FinalStates { get; private set; }public char[] InputChars { get; private set; }private NFAToDFA dfa;public DFAToMFA(NFAToDFA dfa){this.dfa = dfa;this.InputChars = dfa.InputChars;}public IEnumerable<int[]> DFA2MFA(){var states = new List<int[]>();//dfa结束状态集和非结束状态集var allStates = Enumerable.Range(0, dfa.DFA.GetLength(0)).ToArray();var acceptStates = dfa.FinalStates;var nonAcceptStates = (from state in allStateswhere !acceptStates.Contains(state)select state).ToArray();states.Add(nonAcceptStates);states.Add(acceptStates);var compared = new List<int[]>(states);while (true){foreach(var item in states){if (item.Length < 2) continue;for (var i = 0; i < InputChars.Length; ++i){var groups = (from state in itemgroup state by states.FindIndex(array => array.Contains(dfa.DFA[state, i])) into gselect g).ToArray();if (groups.Length < 2) continue;var removeds = (from array in groupsfrom removed in arrayselect removed).ToArray();compared.RemoveAll(array => array.Any(state => removeds.Contains(state)));foreach(var group in groups)compared.Add(group.ToArray());}}if (Equal(states, compared)) break;states.Clear();states.AddRange(compared);}states = (from state in statesorderby state.Min()select state).ToList();//initialize initial & final statesInitialState = states.FindIndex(state => state.Contains(dfa.InitialState));FinalStates = (from final in dfa.FinalStatesselect states.FindIndex(state => state.Contains(final))).Distinct().ToArray();Debug.WriteLine($"MFA Initial State:\t{InitialState}");Debug.WriteLine($"MFA Fnitial State:\t{string.Join(" ", FinalStates)}");CreateMFATable(states);PrintMFATable();return states;}private bool Equal([DisallowNull]IEnumerable<IEnumerable<int>> left, [DisallowNull]IEnumerable<IEnumerable<int>> right){if (left.Count() == 0 && right.Count() == 0) return true;if (left.Count() != right.Count()) return false;foreach (var element in left){var exist = right.Any(item => Enumerable.SequenceEqual(item, element));if (!exist) return false;}foreach (var element in right){var exist = left.Any(item => Enumerable.SequenceEqual(item, element));if (!exist) return false;}return true;}private void CreateMFATable(List<int[]> states){MFA = new int[states.Count(), InputChars.Length];for (var i = 0; i < MFA.GetLength(0); ++i){var state = states[i].Min();for (var j = 0; j < MFA.GetLength(1); ++j){var dfastate = dfa.DFA[state, j];MFA[i, j] = dfastate < 0? dfastate: states.FindIndex(array => array.Contains(dfastate));}}}private void PrintMFATable(){Debug.WriteLine("\nMFA Table");for (var i = 0; i < InputChars.Length; ++i)Debug.Write($"\t{InputChars[i]}");Debug.WriteLine("");for (var i = 0; i < MFA.GetLength(0); ++i){Debug.Write(i);for (var j = 0; j < MFA.GetLength(1); ++j){Debug.Write("\t");if (MFA[i, j] >= 0)Debug.Write($"{MFA[i, j]}");}Debug.WriteLine("");}}}

测试

[TestMethod]
public void DFA2MFATest()
{var regex = "(a|b)*abb";var regexDoted = UseDotForConcatenation(regex);var regexPostfix = InfixToPostfix(regexDoted);var enfa = new RegexToENFA();enfa.Regex2ENFA(regexPostfix);Debug.WriteLine("");var dfa = new NFAToDFA(enfa);var query = from array in dfa.ENFA2DFA()select $"{string.Join(" ", array)}";Debug.WriteLine("\nDFA States");Debug.WriteLine(string.Join(Environment.NewLine, query));Debug.WriteLine("");var mfa = new DFAToMFA(dfa);query = from array in mfa.DFA2MFA()select $"{string.Join(" ", array)}";Debug.WriteLine("\nMFA States");Debug.WriteLine(string.Join(Environment.NewLine, query));
}输出如下：ENFA Initial State:	6
ENFA Final State:	13ENFA Tablea	b	ε
0	1		
1			5
2		3	
3			5
4			0 2
5			4 7
6			4 7
7			8
8	9		
9			10
10		11	
11			12
12		13	
13			DFA Initial State:	0
DFA Final States:	4DFA Tablea	b
0	1	2
1	1	3
2	1	2
3	1	4
4	1	2DFA States
6 4 7 8 0 2
9 1 5 4 7 8 0 2 10
3 5 4 7 8 0 2
3 11 12 5 4 7 8 0 2
13 3 5 4 7 8 0 2MFA Initial State:	0
MFA Final State:	3MFA Tablea	b
0	1	0
1	1	2
2	1	3
3	1	0MFA States
0 2
1
3
4