-
Notifications
You must be signed in to change notification settings - Fork 1
/
DeterminedFiniteAutomaton.cs
217 lines (209 loc) · 8.64 KB
/
DeterminedFiniteAutomaton.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AutomataConverter
{
class DeterminedFiniteAutomaton: NamedAutomaton
{
int startStateIndex;
HashSet<int> finalStates;
/// <summary>
/// Matrix specify all transitions in automata.
/// First index is a state index.
/// Second one is a alphabet's symbol index.
/// Value is a state index, too.
/// int [5,4] == 3 means that
/// there is a transition from 5 to 3 by symbol with index 4.
/// Value is null means that transition by this symbol doesn't exist.
///
/// Первый индекс это состояние из которого исходит переход
/// Второй индекс указывает на символ алфавита по которому осуществляется переход
/// Значение это состояние, в которое входит переход.
/// int[5,4] == 3 означает, что
/// переход из состояния 5 в состояние 3 может осуществляться по символу 4.
/// Если значение null, то это означает, что такого перехода не существует
/// </summary>
List<List<int?>> transitions;
public int NumberOfSymbols
{
get
{
return symbolsNamesMap.Count;
}
}
public int NumberOfStates
{
get
{
return statesNamesMap.Count;
}
}
public override bool IsStateExist(string stateName)
{
return namesStatesMap.Keys.Contains(stateName);
}
public override bool IsSymbolExist(string stateName)
{
return namesSymbolsMap.Keys.Contains(stateName);
}
public void AddStates(IEnumerable<string> newStates)
{
foreach (var state in newStates)
{
AddState(state);
}
}
public void AddSymbols(IEnumerable<string> newSymbols)
{
foreach (var symbol in newSymbols)
{
AddSymbol(symbol);
}
}
/// <summary>
/// Добавить новое состояние.
/// </summary>
/// <param name="name">Имя состояния</param>
/// <exception cref="AutomatonBuildException"></exception>
public override void AddState(string name)
{
if (IsStateExist(name))
{
throw new AutomatonBuildException("State already exist.");
}
namesStatesMap.Add(name, statesNamesMap.Count);
statesNamesMap.Add(name);
List<int?> transitionsFrom = new List<int?>(NumberOfStates);
for (int i = 0; i < NumberOfSymbols; i++)
{
transitionsFrom.Add(null);
}
transitions.Add(transitionsFrom);
}
/// <summary>
/// Добавляет новый переход в автомат
/// </summary>
/// <param name="existingSource">Уже существующая в автомате вершина, из которой переход исходит.</param>
/// <param name="existingDestination">Уже существующая в автомате вершина, в которую переход входит.</param>
/// <param name="existingSymbol">Уже существующий в автомате символ по которому происходит переход.</param>
/// <exception cref="AutomatonBuildException"></exception>
public override void AddTransition(string existingSource, string existingDestination, string existingSymbol)
{
if (!IsStateExist(existingSource))
{
throw new AutomatonBuildException(string.Format("State {0} not exist.", existingSource));
}
if (!IsStateExist(existingDestination))
{
throw new AutomatonBuildException(string.Format("State {0} not exist.",existingDestination));
}
AddTransition(namesStatesMap[existingSource],
namesStatesMap[existingDestination], namesSymbolsMap[existingSymbol]);
}
public bool IsTransitionExist(int source, int symbol)
{
return transitions[source][symbol] != null;
}
public void AddTransition(int existingSource, int existingDestination, int existingSymbol)
{
if (IsTransitionExist(existingSource, existingSymbol))
{
throw new AutomatonBuildException("Transition already exist.");
}
transitions[existingSource][existingSymbol] = existingDestination;
}
/// <summary>
/// Добавляет новый символ в алфавит автомата.
/// </summary>
/// <param name="newSymbol">Имя нового символа.</param>
/// <exception cref="AutomatonBuildException"></exception>
public override void AddSymbol(string newSymbol)
{
if (IsSymbolExist(newSymbol))
{
throw new AutomatonBuildException("Symbol already exist.");
}
namesSymbolsMap.Add(newSymbol, symbolsNamesMap.Count);
symbolsNamesMap.Add(newSymbol);
foreach (var transitionsFromOneState in transitions)
{
transitionsFromOneState.Add(null);
}
}
public void SetFinalStates(HashSet<string> finalStates)
{
SetFinalStates(finalStates.Select((name) => (namesStatesMap[name])));
}
public void SetFinalStates(IEnumerable<int> finalStates)
{
this.finalStates =new HashSet<int> (finalStates);
}
/// <summary>
/// Добавляет уже существующее состояние во мнеожество заключительных
/// </summary>
/// <param name="finalState">Имя, уже существующего, состояния</param>
public void AddToFinalStates(string finalState)
{
AddToFinalStates(namesStatesMap[finalState]);
}
public void AddToFinalStates(int terminalState)
{
finalStates.Add(terminalState);
}
/// <summary>
/// Создаёт ДКА с одним начальным состоянием.
/// </summary>
/// <param name="startState">Имя начального состояния.</param>
public DeterminedFiniteAutomaton(string startState)
{
startStateIndex = 0;
transitions = new List<List<int?>>() { new List<int?>() };
finalStates = new HashSet<int>();
statesNamesMap = new List<string>() { startState };
namesStatesMap = new Dictionary<string, int>();
namesStatesMap.Add(startState, 0);
symbolsNamesMap = new List<string>();
namesSymbolsMap = new Dictionary<string, int>();
}
public string GetTransitionDestination(string source, string symbol)
{
if (!IsSymbolExist(symbol))
{
throw new AutomatonBuildException(string.Format("Automaton's alphabet doesn't contain {0}", symbol));
}
if (!IsStateExist(source))
{
throw new AutomatonBuildException(string.Format("Symbol {0} already exist.", symbol));
}
int? destinationIndex = GetTransitionDestination(namesStatesMap[source],
namesSymbolsMap[symbol]);
if (destinationIndex == null)
{
return null;
}
return statesNamesMap[(int)destinationIndex];
}
public int? GetTransitionDestination(int source, int symbol)
{
return transitions[source][symbol];
}
public override List<string> GetAlphabet()
{
return new List<string>(namesSymbolsMap.Keys.ToList());
}
public override List<string> GetStates()
{
return new List<string>(namesStatesMap.Keys);
}
public string GetStartState()
{
return statesNamesMap[startStateIndex];
}
public override List<string> GetFinalStates()
{
return finalStates.Select((index) => (statesNamesMap[index])).ToList();
}
}
}