広告 基本情報技術者

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

今回のテーマは基本情報技術者試験や応用情報技術者試験で出題されるオートマトンです。
オートマトン?聞きなれない言葉ですね。

問題

入力記号,出力記号の集合が{0,1}であり,状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで,S1は初期状態を表し,グラフの辺のラベルは,入力/出力を表している。

オートマトン

  • ア:0001000110
  • イ:0001001110
  • ウ:0010001000
  • エ:0011111110

基本情報技術者平成30年春期 午前問4 ※図は過去問を参考に作成したものです。

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

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

本記事で学べること

  • オートマトン(有限オートマトン)の状態遷移図と状態遷移表の作り方を理解
  • 基本情報技術者試験の過去問の解き方を学ぶ

オートマトン

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

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

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

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

スポンサーリンク

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

有限オートマトン

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

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

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

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

状態遷移表

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

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

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

状態遷移図

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

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

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

有限オートマトンの例

例題

次の状態遷移表は「すべて数値なら受理」、「数値以外があれば非受理」という有限オートマトンです。この有限オートマトンの状態遷移図を作成せよ。※状態Aを初期状態(開始地点)、受理状態を状態Cとする。

状態遷移表の例

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

手順1 状態A

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

Aの状態遷移

手順2 状態B

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

Bの状態遷移

手順3 状態C

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

Cの状態遷移

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

スポンサーリンク

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

問題

入力記号,出力記号の集合が{0,1}であり,状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで,S1は初期状態を表し,グラフの辺のラベルは,入力/出力を表している。

オートマトン

  • ア:0001000110
  • イ:0001001110
  • ウ:0010001000
  • エ:0011111110

基本情報技術者平成30年春期 午前問4

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

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

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

オートマトンの過去問解説1

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

オートマトンの過去問手順1

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

オートマトンの過去問手順2

 

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

オートマトンの過去問手順3

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

オートマトンの過去問手順4

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

オートマトンの過去問手順1

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

オートマトンの過去問手順2

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

オートマトンの過去問手順3

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

オートマトンの過去問手順5

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

オートマトンの過去問手順4

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

helpful