状態遷移図と状態遷移表｜やさしい基礎理論
2024-09-12 更新
この連載は、基本情報技術者試験の受験者を対象としたものです。
多くの受験者が苦手としている「情報の基礎理論」の分野から毎回１つずつテーマをあげて、やさしくポイント解説と問題解説を行います。
苦手分野を克服して、試験の得点をアップしましょう。
今回のテーマは、 「状態遷移図」と「状態遷移表」 です。
状態遷移図の記述方法
状態遷移図と状態遷移表は、システムがいつかの状態を持ち、外部からの入力によって状態が遷移する（他の状態に移り変わる）ことを示す図表です。
これらは、制御系システムの設計や、文字列の内容の検査などに使われます。
はじめに、状態遷移図の記述方法を説明しましょう。
状態遷移図には、いくつかの形式がありますが、ここでは、後で紹介する過去問題で使われている形式を取り上げます。
状態を円で示し、円と円を結ぶ矢印の付いた線で状態の遷移の向きを示し、矢印の上に遷移のきっかけとなる入力とその際の出力を「入力/出力」という表現で書き添えます。
初期状態には、大きな矢印を書き添えます。終了状態がある場合は、その状態を二重線の円で示します。
図1に状態遷移図の例を示します。
この状態遷移図には、状態0、状態1、状態2という3つの状態があり、大きな矢印を書き添えた状態0が初期状態であり、二重線の円の状態2が終了状態です。
矢印の付いた線が同じ状態に向けられている場合は、その入力があっても状態が遷移しないことを意味します。
状態遷移表の記述方法
次に、状態遷移表の記述方法を説明しましょう。
状態遷移表には、特に決まった形式はないのですが、多くの場合に、表の縦方向の見出しで状態を示し、横方向の見出しで遷移のきっかけとなる入力を示し、縦と横が交差した枠の中に、どの状態に遷移するかを示します。
図2に状態遷移表の例を示します。
この状態遷移表には、状態0（初期状態）、状態1、状態2（終了状態）という3つの状態があります。
たとえば、状態0のときに入力aがあった場合には、それらが交差した枠の中に示された状態1に遷移します。
状態0のときに入力bがあった場合は、それらが交差した枠の中が同じ状態0になっています。これは、その入力があっても状態が遷移しないことを意味します。
状態遷移図に関する問題の例
状態遷移図と状態遷移表に関する問題を2つ紹介しましょう。
はじめは、制御系システムの設計に状態遷移図を使った問題です。
ここでは、300円の商品を販売する自動販売機の動作を、S0、S1、S2という3つの状態を持ち、「入力／出力」を「硬貨の入力／商品の出力」としています。
問1（出典：H28秋問3）
300円の商品を販売する自動販売機の状態遷移図はどれか。ここで、入力と出力の関係を “入力／出力” で表し、入力の “a” は “100円硬貨” を、 “b” は “100円硬貨以外” を示し、S0～S2は状態を表す。入力が “b” の場合はすぐにその硬貨を返却する。また、終了状態に遷移する際、出力の “1” は商品の販売を、 “0” は何もしないことを示す。
この自動販売機では、100円以外の硬貨が入力された（bが入力された）場合には、すぐにその硬貨を返却するとしています。
したがって、300円の商品を販売するには、100円硬貨の入力（aの入力）を3回行い、3回目に商品を出力して初期状態に戻ることになります。
そのための状態遷移図は、大きな矢印が書き添えられた初期状態（0円が入力された状態）でaが入力されたら別の状態（100円が入力された状態）に遷移し、その状態でaが入力されたら別の状態（200円が入力された状態）に遷移し、その状態でaが入力されたら（300円が入力されたら）商品を出力して初期状態に戻る、というものになるので、選択肢アが正解です。
この状態遷移図では、初期状態が終了状態でもあります。
状態遷移表に関する問題の例
次は、文字列の内容の検査に状態遷移表を使った問題です。
ここでは、a（初期状態）、b、c、d、eという5つの状態があり、文字列の内容を検査するときに、たとえば「＋0010」という文字列の場合は、「＋」「0」「0」「1」「0」という文字が順番に入力されたと考えます。
検査中（遷移中）に状態がeになったら不合格（不適切な内容の文字列）なので、不合格にならずにすべての入力が終われば合格（適切な内容の文字列）です。
問2（出典：H26春問5）
表は、文字列を検査するための状態遷移表である。検査では、初期状態をaとし、文字列の検査中に状態がeになれば不合格とする。
解答群で示される文字列のうち、不合格となるものはどれか。ここで文字列は左端から検査し、解答群中の△は空白を表す。
ア ＋0010 イ －1 ウ 12.2 エ 9.△
選択肢アの「＋0010」は、状態a（初期状態）で「＋（符号）」が入力されて状態cに遷移し、状態cで「0（数字）」が入力されて状態bに遷移し、状態bで「0（数字）」が入力されて状態bに遷移し（同じ状態bのまま）、状態bで「1（数字）」が入力されて状態bに遷移し（同じ状態bのまま）、状態bで「0（数字）」が入力されて状態bに遷移し（同じ状態bのまま）、これで文字が終わりなので合格です。
選択肢イの「－1」は、状態a（初期状態）で「－（符号）」が入力されて状態cに遷移し、状態cで「1（数字）」が入力されて状態bに遷移し、これで文字が終わりなので合格です。
選択肢ウの「12.3」は、状態a（初期状態）で「1（数字）」が入力されて状態bに遷移し、状態bで「2（数字）」が入力されて状態bに遷移し（同じ状態bのまま）、状態bで「.（小数点）」が入力されて状態dに遷移し、状態dで「3（数字）」が入力されて状態eに遷移したの不合格です。
選択肢エの「9.△」は、状態a（初期状態）で「9（数字）」が入力されて状態bに遷移し、状態bで「.（小数点）」が入力されて状態dに遷移し、状態dで「△（空白）」が入力されて状態aに遷移し、これで文字が終わりなので合格です。
この問題は、不合格となる文字列を選ぶものなので、選択肢ウが正解です。
基本情報技術者試験の公開問題を見ると、過去問題（過去の試験に出題された問題）の再利用が多いことがわかります。
したがって、試験に合格するために最も効率的で効果的な学習方法は、できなかった問題があれば、できるようになるまで練習することです。
もしも、今回取り上げた問題がすぐにできなかったら、できるようになるまで練習してください。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
