有限オートマトンとは？

決定性有限オートマトンでは、現状態と入力記号の組から次状態が一意に決まる。表の各行をたどり、読み終えた時点の状態が受理状態かどうかで受理・非受理を判定する。 ▍なぜ正解 「10」はS0から入力1でS1へ、続く入力0でS2へ遷移する。最後の状態が受理状態S2なので、この文字列は受理される。 ▍よくある間違い 途中でS2を通過すれば受理と誤ったり、遷移表の入力0列と入力1列を取り違える。 ▍試験の狙い オートマトンの問題は初期状態から鉛筆で状態を書き換えながら1記号ずつ追う。