【基本情報技術者試験】オートマトン

今回のテーマは基本情報技術者試験や応用情報技術者試験で出題されるオートマトンです。

オートマトン？聞きなれない言葉ですね。

聞きなれない言葉である「オートマトン」、基本情報技術者試験の過去問を見ると難しく感じる問題ですが、「オートマトン」の動きを理解してしまえば、簡単に解くことができます。

本記事では「オートマトン」について図解で分かりやすく解説しています。

オートマトン

オートマトン（英：automaton）とは、自動人形という意味を持つ言葉であり、コンピュータの状態、遷移をモデル化したものです。

オートマトンの説明でよく使われるのが自動販売機です。自動販売機は次のように何かしらの操作（入力）をすると状態が遷移します。

• 「お金を入れる」（入力）→「ボタンが点灯」（状態の遷移）
• 「ボタンを押す」（入力）→「ジュースが出てくる」（状態の遷移）

このようにコンピュータの状態遷移をモデル化したのがオートマトンです。

スポンサーリンク

オートマトンにはいくつかの種類があり、その中でも代表的なモデルが「有限オートマトン」です。

有限オートマトン

有限オートマトン（英：finite automaton）とは、状態や遷移の数が有限個であらわされるオートマトンのことです。

有限オートマトンは「状態遷移表」と「状態遷移図」を用いて表現します。

有限オートマトンの状態遷移表

有限オートマトンの状態遷移表は次のとおりです。

• 「状態A」のときに「入力X」が入力されると「状態B」に遷移、「入力Y」が入力されると「状態C」に遷移する
• 「状態B」のときに「入力X」が入力されると「状態C」に遷移、「入力Y」が入力されると「状態A」に遷移する
• 「状態C」のときに「入力X」が入力されると「状態C」のままとなり、「入力Y」が入力されると「状態B」に遷移する

有限オートマトンの状態遷移図

有限オートマトンの状態遷移図は次のとおりです。状態遷移表を図にしたのが状態遷移図です。

状態遷移図は、次の記号で表現します。

名称	記号	説明
状態		状態をあらわす
受理状態		受理状態をあらわす
遷移		遷移をあらわす

有限オートマトンには「受理」と「非受理」があり、入力終了時に受理状態であれば受け付けを完了し、受理状態でないものは非受理となり受け付けません。

有限オートマトンの例

それでは、有限オートマトンの状態遷移図を作成していきます。

手順1 状態A

まずは「状態A」の遷移を追加します。数字が入力された場合は「状態C」、数字以外が入力された場合は「状態B」に遷移するので、それぞれ次のように遷移を追加します。

手順2 状態B

続いては「状態B」、数字または数字以外が入力されたときは、どちらも「状態B」のままなので、次のように遷移を追加します。

手順3 状態C

最後に「状態C」の遷移を追加します。数字が入力された場合は「状態C」のまま、数字以外が入力された場合は「状態B」に遷移するので、それぞれ次のように遷移を追加します。

これで状態遷移図は完成です。

スポンサーリンク

基本情報技術者試験 過去問の解説

この問題はS1を開始地点とし「0011001110」の入力記号どおりに遷移し、その結果得られる出力記号を求めます。

開始地点S1から順に遷移していきます。

まずは入力「0」に対する出力は「0」（入力データ「0011001110」、出力データ「0」）

続いて入力「0」に対する出力は「0」（入力データ「0011001110」、出力データ「00」）

続いて入力「1」に対する出力は「0」（入力データ「0011001110」、出力データ「000」）

続いて入力「1」に対する出力は「1」（入力データ「0011001110」、出力データ「0001」）

続いて入力「0」に対する出力は「0」（入力データ「0011001110」、出力データ「00010」）

続いて入力「0」に対する出力は「0」（入力データ「0011001110」、出力データ「000100」）

続いて入力「1」に対する出力は「0」（入力データ「0011001110」、出力データ「0001000」）

続いて入力「1」に対する出力は「1」（入力データ「0011001110」、出力データ「00010001」）

続いて入力「1」に対する出力は「1」（入力データ「0011001110」、出力データ「000100011」）

最後に入力「0」に対する出力は「0」（入力データ「0011001110」、出力データ「0001000110」）

出力データは「0001000110」となり「ア」が正解です。