Type Reference
Source SLScanner/FiniteAutomaton.cpp
Source SLScanner/DeterministicFiniteAutomaton.cpp
Test SLScanner/TestDeterministicFiniteAutomaton.cpp

## Definition

$S$ is the finite set of states in the recognizer, along with an error state $s_e$

$\Sigma$ is the finite alphabet used by the recognizer. Typically, $\Sigma$ is the union of the edge labels in the transition diagram.

$\delta(s, c)$ is the recognizer’s transition function. It maps each state $c\in \Sigma$ and each character $c ∈ \Sigma$ into some next state. In state si with input character $c$, the $FA$ takes the transition $s_i\rightarrow^c \delta (s_i, c)$.

$s_0\in S$ is the designated start state.

$S_A$ is the set of accepting states, $S_A\subseteq S$. Each state in $S_A$ appears as a double circle in the transition diagram.

## Design

According to the definition of Finite Automaton, I have designed the class FiniteAutomaton in below structure. Actually, starting state $s_0$ is always $s_0$, so I didn’t describe it explicitly in the class. Before building the class structrue, I decided to define some fundamental types for the internal elements of a finite automaton.

typedef int32_t State;
typedef char Alphabet;
typedef std::pair<State, Alphabet> Move;
typedef std::map<Move, State> TransitionSet;
typedef std::set<State> StateSet;
typedef std::set<Alphabet> AlphabetSet;
typedef enum {
Accepted = 1, NotAccepted = 0, Trapped = -1
} StateType;


Followings are some necessary elements for a finite automaton.

StateSet states;
TransitionSet transitions;
AlphabetSet alphabets;
StateSet acceptingStates;
State currentState;


And those values has been defined outside the FiniteAutomaton class.

const FiniteAutomaton::State StartState = 0;
const FiniteAutomaton::State TrapState = -1;


The FiniteAutomaton class is a base class for DeterministicFiniteAutomaton. And we can only use DFA to match the strings. So the most important part of the scanner is the fundamental DFA.

So I built the following function to simulate the actions of real DFA.

State transite(Alphabet input);

Silly::DeterministicFiniteAutomaton::State
Silly::DeterministicFiniteAutomaton::transite(Silly::DeterministicFiniteAutomaton::Alphabet input) {
if (isFinished) {
reboot();
isFinished = false;
}
if (alphabets.find(input) != alphabets.end() && transitions.find(Move(currentState, input)) != transitions.end()) {
State nextState = transitions[Move(currentState, input)];
currentState = nextState;
currentAlphabet = input;
return nextState;
} else {
currentState = TrapState;
return TrapState;
}
}


The transite function needs to check if the DFA has finished a match task executed by match function. And one transition means finding an accessible transition from all transitions. If it does not exist in the transitions, the DFA may cause a trap state to exclaim the match is not successful and it can not move to other states unless reboot is executed.

Actually the structure of a DFA is simple and you must manually set all the elements for the DFA by using the following constructor function.

DeterministicFiniteAutomaton(
StateSet states_,
TransitionSet transitions_,
AlphabetSet alphabets_,
StateSet acceptingStates_);


## Test

So I used following test case to check the availability of the DFA.

DeterministicFiniteAutomaton.SimpleTest:

Test Result:

String StateType TestResult
A12345 Accepted PASS
A Accepted PASS
Z3910 Accepted PASS
Z99999 Accepted PASS
Z9999D Trapped PASS
Trapped PASS
3232 Trapped PASS

DeterministicFiniteAutomaton.FloatNumberTest:

The definition of test DFA is omitted, you can reference it in the SLScanner/TestDeterministicFiniteAutomaton.cpp.

String StateType TestResult
0.13423231 Accepted PASS
0.1342E+213.4 Accepted PASS
+13 Accepted PASS
+13e-19 Accepted PASS
.234144 Trapped PASS
.234122.21310012. Trapped PASS
.234E NotAccepted PASS

DeterministicFiniteAutomaton.CamelCaseTest:

The definition of test DFA is omitted, you can reference it in the SLScanner/TestDeterministicFiniteAutomaton.cpp.

String StateType TestResult
HelloWorld Accepted PASS
GoodBoy Accepted PASS
GoodB NotAccepted PASS
GoodB8 Trapped PASS