【問題】
次の表は、入力記号の集合が{0，1}、状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
0 1
━ ━
a ┃ a b
b ┃ c d
c ┃ a b
d ┃ c d
【解答】
どれかをスタートにして、110を実際に入力してみれば良い。
例えばaを初期とすると、ｂ → ｄ → ｃとなり、ｃを受理すれば良いことが分かる。
例えばbを初期とすると、ｄ → ｄ → ｃとなり、やはりｃを受理すればよいことが分かる。
よって、ｃを受理状態とすればよい。