有限オートマトンをこのように図示したとき、頂点r0からr1,r2,…を経てrnへ至る‘道’は
δ(ri-1,ai)=ri (i=1,2,…,n)
というnステップの状態遷移を表す。両端のみに注目すれば
δ(δ(…δ(δ(r0,a0),a1),…),an)=rn
これを簡単に
δ*(r0,a0…an)=rn
で表す。
δ*(q0,x) は有限オートマトンMが初期状態q0から動き始めて、入力語xを読み終わったときの状態。
定義:この状態 δ*(q0,x)∈F のとき、Mは語xを受理するという。Mが受理する語の集合をMの受理集合といいL(M)で表す。
先程の例だと、L(M)={0,1,2}=Q となって、あまり面白くない。