九工大 情報工学府 専門科目（知能情報工学） 2026年度 院試 過去問 解答例・解説（全2問）

合同で状態を作る

$L_3$ は「差そのもの」ではなく「差の3での剰余」だけを覚えればよい。有限オートマトンで扱えるのは有限個の記憶なので、剰余類を状態にするのが自然である。

非正規性の見方

$L_0$ では、0の数と1の数の差をぴったり0に戻す必要がある。読んだ0の個数がどれだけ多いかを無制限に覚えなければならないため、有限状態では足りない。この直観を、マイヒル--ネロードの有限指数性に反する形で答案化する。

採点上の注意

1--3は図だけでなく、状態が何を表すかを書くと遷移の向きの誤りを減らせる。1--4は「非正規」とだけ書いても不十分で、無限個の $0^i$ から同じ同値類に入る2語を選び、右側に $1^i$ を足して矛盾を作るところまで必要である。

クラス変数とインスタンス変数

stID や score は学生ごとに異なるのでインスタンス変数である。一方、登録人数は全学生を通じて1つだけ持つ値なので static を付ける。ここを取り違えると、学生ごとに count が別々に増減してしまう。

オーバーロードの採点ポイント

問題3では、メソッド名は同じ setCredit のまま、仮引数型だけを double にする。戻り値型だけを変えてもJavaではオーバーロードにならない。

計算量の典型ミス

途中終了フラグがあるからといって、最悪計算量が $O(n)$ になるわけではない。最悪の場合は毎回どこかで交換が起こり、最後まで二重ループが走る。最良の場合と最悪の場合を分けて書くと、答案が安定する。