有限オートマトン（finite automaton）は、5個組 (Q,Σ,δ,q0,F) である ここで、 Q は状態と呼ばれる有限集合 Σ はアルファベットと呼ばれる有限集合 δ:Q×Σ→Q は遷移関数 q0∈Q は開始状態 F⊆Q は受理状態の集合 とする。