Here, I provide C++ implementation of a table-based Deterministic Finite Automaton. A DFA is a finite state machine that accepts/rejects finite strings of symbols and has a unique transition from each state on each input symbol.
A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of
- a finite set of states (Q)
- a finite set of input symbols called the alphabet (Σ)
- a transition function (δ : Q × Σ → Q)
- a start state (q0 ∈ Q)
- a set of final/accept states (F ⊆ Q)
Let w = a1a2 … an be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r0,r1, …, rn, exists in Q with the following conditions:
- r0 = q0
- ri+1 = δ(ri, ai+1), for i = 0, …, n−1
- rn ∈ F.
The first condition says that the machine starts in the start state q0. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).
Take a look at the C++ implementation. It requires a single pass over the input strings to decide whether or not they belong to the language of a given DFA.