問題
入力記号，出力記号の集合が{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」に遷移するので、それぞれ次のように遷移を追加します。
手順2 状態B
続いては「状態B」、数字または数字以外が入力されたときは、どちらも「状態B」のままなので、次のように遷移を追加します。
手順3 状態C
最後に「状態C」の遷移を追加します。数字が入力された場合は「状態C」のまま、数字以外が入力された場合は「状態B」に遷移するので、それぞれ次のように遷移を追加します。
スポンサーリンク
基本情報技術者試験 過去問の解説
問題
入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，S1は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。
- ア：0001000110
- イ：0001001110
- ウ：0010001000
- エ：0011111110
基本情報技術者平成30年春期 午前問4
この問題は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」）
基本情報技術者試験おすすめの参考書・問題集
| いちばんやさしい 基本情報技術者 | 『基本情報技術者試験』試験に、短期間で一発合格するための試験対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。 |
| かやのき先生の基本情報技術者教室 | 基本情報技術者をめざす方のためのやさしいオールインワンタイプの参考書＆問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。 |
| 基本情報技術者 パーフェクトラーニング過去問題集 | 科目A・Bともに万全の対策ができる、定番の過去問題集！科目A・科目Bの両方について万全の対策ができる。 |
| キタミ式イラストIT塾 基本情報技術者 | すべての解説をイラストベースで行っているため，とてもわかりやすい解説本。いちばん最初に読む基本情報技術者試験関連の書籍を探している人におすすめ！ |
| 出るとこだけ！基本情報技術者［科目B］ | 基本情報技術者【科目Ｂ】対策の定番書！前提知識＋解き方＋試験問題を掲載。効率よく学習できる。 |
| 基本情報技術者 合格教本 | 出題範囲を体系的にきちんと理解しながら学習したい人におすすめ！基本情報技術者試験の定番テキストの改訂版。 |
| 基本情報技術者 超効率の教科書＋よく出る問題集 | 動画でスムーズに学習スタート、テキストでしっかり理解度を深める！よく出る問題を反復学習することで、合格に直結するチカラが身に付く！ |