科目Bの状態遷移問題の解き方｜いまの状態と入力を表で追う

表を引いて状態を変えるだけ、と言われても、いまどこにいるのか途中で分からなくなる。

科目Bで、状態遷移表を使って文字列を判定するコードを見て、手が止まったことはありませんか？

if 文がほとんど無いのに、2次元配列の添字だけで処理が進んでいくので、何が起きているのかつかみにくい形です。状態の番号と文字の種類の番号が混ざってしまい、どの行のどの列を見ているのかを見失う人も多いのではないでしょうか。

大丈夫です。状態遷移の問題は、1文字読むたびに、いまの状態と文字の種類と次の状態を1行ずつ表に書けば、必ず同じ答えにたどり着けます。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。注文や申し込みのように、受付から完了までいくつもの段階を進むデータは、実務でも状態遷移として管理することがよくあります。

あるとき、キャンセルしたはずの注文が、発送済みの状態に戻ってしまう不具合に出会いました。原因は、キャンセルから発送へ移る遷移を禁止していなかったことで、状態と操作の組み合わせを表に書き出してようやく抜けに気づけました。

この記事では、状態遷移の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

状態遷移の問題は何を聞いているのか¶

最初に、状態遷移とは何かを短く押さえておきましょう。状態遷移とは、いまの状態と読み込んだ入力の組み合わせだけで、次の状態が1つに決まる仕組みのことです。

文字列を1文字ずつ読みながら、この仕組みで状態を移していくものは、有限オートマトンと呼ばれることもあります。名前は難しそうですが、すごろくのマスを1つずつ進むのとよく似ています。

すごろくでは、いまいるマスと出た目で、次に進むマスが決まりました。状態遷移でも、いまの状態と読んだ文字の種類で、次の状態が決まります。

そして、最後の文字を読み終えたときにゴールのマスにいれば合格、それ以外なら不合格と判定します。このゴールにあたる状態を、受理状態と呼びます。

状態遷移表の読み方¶

状態遷移の問題では、どの状態でどの入力が来たらどこへ移るのかが、表で与えられます。行が今の状態、列が入力の種類、マスの中身が次の状態、という形がもっとも多い書き方です。

この記事の例題では、文字列が整数として正しい形かどうかを判定します。先頭に符号が1つあってもよく、そのあとに数字が1個以上続く形だけを正しいとみなします。

たとえば状態1で数字を読んだら、表の1行目の数字の列を見て、状態3へ移ります。状態4は一度入ると二度と出られない行で、形が崩れた時点でここへ落ちる仕組みです。

設問のパターンを表で整理する¶

状態遷移の設問は、聞かれ方がいくつかの型に分かれます。どの型なのかを最初に見極めると、表のどの列を見ればよいかがはっきりします。

この記事では、出題されやすい判定の結果と表の空欄を中心に追います。途中の状態を問う型は、同じトレース表の途中の行を読むだけで答えられます。

まず目を付ける場所¶

状態遷移の考え方がつかめたら、次はコードのどこから読むかを決めます。この問題で目を付ける場所は3つです。

ひとつ目は状態の初期値、ふたつ目は遷移表を引く添字の順番、みっつ目はループのあとでどの状態を受理としているかです。この3か所が決まれば、あとは1文字ずつ表に書くだけです。

状態の初期値はどこから始まるか¶

最初に確かめたいのが、ループに入る前に状態を表す変数へ入れている値です。多くの問題では、読み始めの状態として1や0が入っています。

この初期値は、空の文字列を入れたときの答えにそのまま関わります。1文字も読まなければ状態は初期値のままなので、初期値が受理状態でない限り、空の文字列は false になります。

遷移表を引く添字の順番¶

次に見るのが、t[state, k] のように遷移表を引いている行です。1つ目の添字が状態で行を選び、2つ目の添字が文字の種類で列を選んでいます。

この順番が逆になると、まったく違うマスを読んでしまいます。2次元配列の行と列の取り違えに不安がある場合は、こちらの記事で確かめておくと安心です。

【関連記事】科目Bの2次元配列問題の解き方｜行と列を表にして追う方法

受理状態の判定はループの外にあるか¶

みっつ目は、どの状態なら true を返しているかです。この例題では、状態3だけが受理状態です。

もうひとつ大事なのが、その判定がループの外にあることです。途中で受理状態を通っても、最後の文字を読み終えたときにそこにいなければ、正しい文字列とはいえません。

例題：文字列が整数の形かを判定する関数¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、文字列 str が整数として正しい形かどうかを判定し、正しければ true を返す関数です。関数 charType は、文字を受け取り、符号なら1、数字なら2、それ以外なら3を返すものとします。

○論理型: isInteger(文字列型: str)
  整数型の二次元配列: t ← {{2, 3, 4}, {4, 3, 4}, {4, 3, 4}, {4, 4, 4}}
  整数型: state ← 1
  整数型: i, k
  for (i を 1 から str の文字数 まで 1 ずつ増やす)
    k ← charType(str の i 文字目)
    state ← t[state, k]
  endfor
  if (state が 3 と等しい)
    return true
  else
    return false
  endif

t は先ほどの状態遷移表をそのまま2次元配列にしたものです。t[2, 1] なら、状態2で符号を読んだときの次の状態、つまり4を表します。

では、str が "-305" のとき、isInteger の戻り値はどうなるでしょうか？ あわせて "+-7" と "-" のときも考えてみてください。

トレース表で状態の移り変わりを追う¶

頭の中だけで状態を移していくと、いまの状態の番号と文字の種類の番号が混ざってしまいます。そこで、1文字ぶんの処理を1行として、i、読んだ文字、k、遷移する前の状態、引いたマス、遷移したあとの状態をトレース表に書きます。

ポイントは、遷移する前の状態と遷移したあとの状態を別の列に分けることです。こうすると、次の行の前の状態が、1つ上の行のあとの状態と同じになっているかで、書き間違いにすぐ気づけます。

4文字を読み終えたとき、state は3です。3は受理状態なので、"-305" の戻り値は true になります。

3行目と4行目を見てください。状態3で数字を読むと、また状態3に戻っています。数字がいくつ続いても同じマスにとどまるので、桁数に関係なく判定できるのです。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

false になる文字列も同じ表で追う¶

次に "+-7" を追ってみましょう。1文字目の ＋ で状態1から2へ、2文字目の − で t[2, 1] を引いて状態4へ移ります。

状態4はどの列を引いても4なので、3文字目の 7 を読んでも4のままです。最後の状態が3ではないので、戻り値は false になります。

"-" だけのときは、1文字目で状態2へ移ったところで文字列が終わります。状態2は受理状態ではないので、符号だけの文字列は false です。

表の空欄はその状態の意味から考える¶

遷移表の一部が空欄になっている問題では、マスの番号を計算で出そうとしないことが大切です。その状態がどんな意味を持っているかを言葉にすると、入る番号が自然に決まります。

たとえば状態2の数字の列が空欄なら、符号を読んだあとに数字が来た場面です。これは正しい形が始まったところなので、数字を読んでいる状態3が入ります。

文字列を1文字ずつ取り出す処理そのものに不安がある場合は、こちらの記事が役に立ちます。

【関連記事】科目Bの文字列問題の解き方｜1文字ずつ取り出す処理を追うコツ

間違いやすい選択肢の見分け方¶

状態遷移の問題では、受理状態の範囲や判定の場所を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題のコードを使って、よくある誤りを表にまとめました。どれも、そのとおりに動かすと正しい答えと食い違う入力があります。

2行目の誤りは、途中で一度でも受理状態を通れば合格にしてしまう形です。"3a" は2文字目の a で状態4へ落ちるので、本当は false でなければなりません。

4行目は、行と列を取り違えたときに起きます。t は4行3列なので、状態の番号を2つ目の添字に入れると、状態4のときに存在しない列を引こうとしてしまいます。

選択肢の文字列は短いものから試す¶

受理される文字列を選ぶ問題では、選択肢を1つずつトレース表で追うのが確実です。そのとき、短い文字列から順に試すと、早い段階で状態4に落ちるものを外せます。

状態4のように抜け出せない状態があるなら、そこへ落ちた時点で残りの文字を読む必要はありません。最後まで4のままだと分かっているので、すぐに false と決められます。

表をフローチャートのように描いてみる¶

状態の数が増えて表だけでは追いにくいときは、状態を丸、遷移を矢印にして図に描き起こすのも効果的です。矢印に、どの入力で移るのかを書き添えておくと、行き止まりや抜けがひと目で分かります。

コードを図に描き起こす考え方は、フローチャートとの比べ方を扱ったこちらの記事でも紹介しています。

【関連記事】擬似言語とフローチャートの違いとは？図に描き起こして理解する方法

状態遷移表は、if 文を表の形に置き換えたものだと考えることもできます。同じ判定を if 文で書くとどうなるかを比べたい人は、条件分岐の解き方の記事もあわせて読んでみてください。

【関連記事】科目Bの条件分岐問題の解き方｜どの枝を通るかを表で追う

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。変数の値が表の中を飛び回るような処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの文字で予想とずれたのかがすぐに分かります。

試すときは、まず "-305" を動かして、1文字ごとに state が 1、2、3、3、3 と移る様子を確かめてください。そのあと最後の判定を if 文ごとループの中へ移して "3a" を動かすと、途中で true を返してしまう様子が見え、判定の場所の意味が体で分かります。

慣れてきたら、小数点を1つだけ許すように状態を1つ増やすなど、遷移表を自分で書き換えてみましょう。表を変えたら結果がどう変わるかを予想してから動かす練習がおすすめです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、文字を読むたびに状態の番号が移り変わっていく流れを確かめてみてください。

まとめ¶

科目Bの状態遷移の問題は、特別な知識を問うものではありません。いまの状態と入力で表を引き、次の状態に置き換える、という手順を1文字ずつ表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、状態が3つか4つくらいの小さな表で十分です。何度か表を書くうちに、遷移表を見ただけで、どんな文字列が受理されるのかが分かるようになります。

表は今の状態で行を選び、入力で列を選ぶ。合否は最後の文字を読み終えてから決める。 この2つを習慣にしておけば、状態遷移の問題にも自信を持って向き合えます。次に遷移表を引くコードを見かけたら、まずは状態の初期値と受理状態から確かめてみてください。