状態遷移表を使って文字列を検査する問題をやさしく解説
基本情報技術者試験では、文字列を左から順番に読み取りながら、現在の状態を変化させていく問題が出題されます。
このような問題では、状態遷移表や状態遷移図を使って、文字列が条件を満たしているかどうかを判定します。
今回は、状態遷移表を使って、どの文字列が不合格になるかを考える問題です。
問題
表は、文字列を検査するための状態遷移表である。
検査では、初期状態を a とし、文字列の検査中に状態が e になれば不合格とする。
解答群で示される文字列のうち、不合格となるものはどれか。
ここで、文字列は左端から検査し、解答群中の△は空白を表す。
| 現在の状態 | 空白 | 数字 | 符号 | 小数点 | その他 |
|---|---|---|---|---|---|
| a | a | b | c | d | e |
| b | a | b | e | d | e |
| c | a | b | e | d | e |
| d | a | e | e | e | e |
解答群
ア +0010
イ -1
ウ 12.2
エ 9△
状態遷移表とは何か
状態遷移表とは、簡単に言うと、
今いる場所と、次に読んだ文字によって、次にどこへ行くかを決める表
です。
例えば、現在の状態が a で、次に読んだ文字が「符号」だったとします。
このとき、表の
行 a × 列 符号を見ます。
表を見ると、行 a、列 符号 のところは c です。
つまり、
a → cに状態が変わります。
状態遷移表は、文字列を読むためのルート表のようなものです。
状態 e は不合格を表す
この問題で一番大事なのは、状態 e の意味です。
状態 e は、検査失敗、つまり不合格状態です。
途中で一度でも e に入ったら、その時点で不合格です。
逆に、最後まで読んでも e に入らなければ合格です。
a〜d：まだ合格の可能性がある状態
e ：不合格状態ここを最初に押さえると、問題がかなり楽になります。
表ではなく「道をたどる」と考える
初学者にとって、状態遷移表は少し読みにくいです。
そこで、右上のイラストのように、状態を丸で表した図として考えると分かりやすくなります。
例えば、
a で数字を読む → b に進む
b で小数点を読む → d に進む
d で数字を読む → e に進むというように、文字を読むたびに、状態という場所を移動していきます。
これは、すごろくや迷路に近い感覚です。
読んだ文字が、次に進む道を決めると考えるとよいです。
選択肢ア「+0010」を確認する
まず、アの +0010 を確認します。
最初の状態は a です。
開始：a
+ ：符号 a → c
0 ：数字 c → b
0 ：数字 b → b
1 ：数字 b → b
0 ：数字 b → b最後まで読んでも、状態 e にはなっていません。
したがって、アは合格です。
ア +0010 → 合格符号の後に数字が続いているので、この表では問題なく受け入れられます。
選択肢イ「-1」を確認する
次に、イの -1 を確認します。
開始：a
- ：符号 a → c
1 ：数字 c → bこちらも、途中で状態 e になっていません。
したがって、イも合格です。
イ -1 → 合格符号が1つあり、その後に数字が来ているので、これも問題ありません。
選択肢ウ「12.2」を確認する
次に、ウの 12.2 を確認します。
ここがこの問題のポイントです。
開始：a
1 ：数字 a → b
2 ：数字 b → b
. ：小数点 b → d
2 ：数字 d → e小数点を読んだ時点では、状態は d です。
まだ不合格ではありません。
しかし、その次に数字の 2 を読むと、
d → eとなります。
状態 e は不合格状態なので、この時点で検査失敗です。
したがって、ウは不合格です。
ウ 12.2 → 不合格
選択肢エ「9△」を確認する
最後に、エの 9△ を確認します。
△は空白を表します。
開始：a
9 ：数字 a → b
△：空白 b → a途中で状態 e になっていません。
したがって、エは合格です。
エ 9△ → 合格空白を読むと状態が戻る場合もあります。
このように、空白だから必ず不合格になるとは限りません。
あくまで、表に従って判断します。
答え
不合格になるのは、次の選択肢です。
ウ 12.2理由は、小数点の後に数字を読んだとき、状態が e になるからです。
1 ：a → b
2 ：b → b
. ：b → d
2 ：d → eしたがって、答えは ウ です。
この問題で大切な考え方
この問題では、文字列そのものを見て、
これは正しそう
これは変そうと感覚で判断してはいけません。
大切なのは、次の手順です。
1. 最初の状態 a から始める
2. 文字を左から1文字ずつ読む
3. 現在の状態と文字の種類で表を見る
4. 次の状態へ移動する
5. e になったら不合格
6. 最後まで e にならなければ合格この手順を守れば、状態遷移表の問題は確実に解けます。
初学者がつまずきやすいポイント
この問題でつまずきやすいのは、12.2 を普通の小数として見てしまうことです。
日常的には、12.2 は正しい数値に見えます。
しかし、この問題では、一般的な数値のルールではなく、問題で与えられた状態遷移表のルールがすべてです。
つまり、
現実の感覚ではなく、表に従うことが大切です。
表では、状態 d のときに数字を読むと e になります。
だから、12.2 は不合格になります。
状態遷移表はプログラムの if 文に近い
状態遷移表は、プログラムで書くと、次のような考え方に近いです。
現在の状態が a で、読んだ文字が数字なら b へ
現在の状態が b で、読んだ文字が小数点なら d へ
現在の状態が d で、読んだ文字が数字なら e へつまり、状態遷移表は、
現在の状態
読んだ文字
次の状態をまとめたものです。
プログラムで文字列チェックを行うときにも、この考え方は使われます。
オートマトンとして考える
このような仕組みは、情報処理の分野ではオートマトンと呼ばれます。
オートマトンは、入力された文字を1つずつ読みながら、状態を変化させていく仕組みです。
今回の問題では、
文字列を読む
状態を変える
不合格状態 e に入るかどうかを確認するという流れになっています。
基本情報技術者試験では、難しい理論を問うというよりも、表や図を正しくたどれるかが問われます。
まとめ
状態遷移表の問題は、見た目よりも手順が大切です。
今回の問題では、最初の状態は a です。
文字を左から順に読み、表に従って状態を変えていきます。
状態 e になったら不合格です。
各選択肢を確認すると、
ア +0010 → 合格
イ -1 → 合格
ウ 12.2 → 不合格
エ 9△ → 合格となります。
したがって、答えは、
ウ 12.2です。
この問題を解くコツは、文字列を見た目で判断するのではなく、状態遷移表というルールブックを1文字ずつたどることです。