@@ -4,14 +4,14 using System.Collections.Generic; | |||||
4 | using System.Linq; |
|
4 | using System.Linq; | |
5 |
|
5 | |||
6 | namespace Implab.Automaton { |
|
6 | namespace Implab.Automaton { | |
7 |
public class DFATransitionTable |
|
7 | public class DFATransitionTable : IDFATableBuilder { | |
8 | DFAStateDescriptior[] m_dfaTable; |
|
8 | DFAStateDescriptior[] m_dfaTable; | |
9 |
|
9 | |||
10 | int m_stateCount; |
|
10 | int m_stateCount; | |
11 | int m_symbolCount; |
|
11 | int m_symbolCount; | |
12 | int m_initialState; |
|
12 | int m_initialState; | |
13 |
|
13 | |||
14 |
readonly |
|
14 | readonly HashSet<int> m_finalStates = new HashSet<int>(); | |
15 | readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); |
|
15 | readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); | |
16 |
|
16 | |||
17 |
|
17 | |||
@@ -32,10 +32,10 namespace Implab.Automaton { | |||||
32 | public bool IsFinalState(int s) { |
|
32 | public bool IsFinalState(int s) { | |
33 | Safe.ArgumentInRange(s, 0, m_stateCount, "s"); |
|
33 | Safe.ArgumentInRange(s, 0, m_stateCount, "s"); | |
34 |
|
34 | |||
35 |
return m_finalStates.Contains |
|
35 | return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s); | |
36 | } |
|
36 | } | |
37 |
|
37 | |||
38 |
public IEnumerable< |
|
38 | public IEnumerable<int> FinalStates { | |
39 | get { |
|
39 | get { | |
40 | return m_finalStates; |
|
40 | return m_finalStates; | |
41 | } |
|
41 | } | |
@@ -55,8 +55,8 namespace Implab.Automaton { | |||||
55 |
|
55 | |||
56 | #endregion |
|
56 | #endregion | |
57 |
|
57 | |||
58 |
protected virtual DFAStateDescriptior |
|
58 | protected virtual DFAStateDescriptior[] ConstructTransitionTable() { | |
59 |
var dfaTable = new DFAStateDescriptior |
|
59 | var dfaTable = new DFAStateDescriptior[m_stateCount]; | |
60 |
|
60 | |||
61 | foreach (var pair in m_finalStates) { |
|
61 | foreach (var pair in m_finalStates) { | |
62 | var idx = pair.Key; |
|
62 | var idx = pair.Key; |
@@ -1,22 +1,14 | |||||
1 | using System; |
|
1 | using System; | |
|
2 | using System.Collections.Generic; | |||
2 |
|
3 | |||
3 | namespace Implab.Automaton { |
|
4 | namespace Implab.Automaton { | |
4 | public interface IDFATableBuilder : IDFATable { |
|
5 | public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> { | |
5 | /// <summary> |
|
6 | /// <summary> | |
6 | /// Marks the state as final. |
|
7 | /// Marks the state as final. | |
7 | /// </summary> |
|
8 | /// </summary> | |
8 | /// <param name="state">State.</param> |
|
9 | /// <param name="state">State.</param> | |
9 | void MarkFinalState(int state); |
|
10 | void MarkFinalState(int state); | |
10 |
|
11 | |||
11 | /// <summary> |
|
|||
12 | /// Defines the transition from <paramref name="s1"/> to |
|
|||
13 | /// <paramref name="s2"/> with input <paramref name="symbol"/>. |
|
|||
14 | /// </summary> |
|
|||
15 | /// <param name="s1">S1.</param> |
|
|||
16 | /// <param name="s2">S2.</param> |
|
|||
17 | /// <param name="symbol">Symbol.</param> |
|
|||
18 | void DefineTransition(int s1, int s2, int symbol); |
|
|||
19 |
|
||||
20 | void SetInitialState(int s); |
|
12 | void SetInitialState(int s); | |
21 |
|
13 | |||
22 | } |
|
14 | } |
@@ -8,6 +8,11 namespace Implab.Automaton { | |||||
8 | /// <summary> |
|
8 | /// <summary> | |
9 | /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index. |
|
9 | /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index. | |
10 | /// </summary> |
|
10 | /// </summary> | |
|
11 | /// <remarks> | |||
|
12 | /// Indexed alphabets are usefull in bulting efficient translations from source alphabet | |||
|
13 | /// to the input alphabet of the automaton. It's assumed that the index to the symbol match | |||
|
14 | /// is well known and documented. | |||
|
15 | /// </remarks> | |||
11 | public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> { |
|
16 | public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> { | |
12 | int m_nextId = 1; |
|
17 | int m_nextId = 1; | |
13 | readonly int[] m_map; |
|
18 | readonly int[] m_map; |
General Comments 0
You need to be logged in to leave comments.
Login now