A finite-state automaton M = (S, I, f, s0
, F) consists of a finite set S of states, a finite input alphabet I, a
transition function f that assigns a next state to every pair of state and input (so that f : S
I S), an initial
or start state s0
, and a subset F of S consisting of final (or accepting states).