有限オートマトンをこのように図示したとき、頂点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 となって、あまり面白くない。

Post filed under 自習.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です