Definition

Let M = (Q, Σ, δ, q₀ F) be a finite state automaton, where

• Q is a finite set of states
• Σ is a finite set of input symbols
• δ is a transition function, δ: Q×Σ →Q
• q₀∈Σ is the start state
• F ⊆ Q is the set of accepting states.