基礎理論
基本情報技術者試験｜入力された0と1の並びについて、これまでに読み込んだ1の個数が偶数か奇数かを判定する有限オートマトンを設計する場…
入力された0と1の並びについて、これまでに読み込んだ1の個数が偶数か奇数かを判定する有限オートマトンを設計する場合、最低限必要な状態の数はいくつか。
ア判定には3状態が必要となる
イ入力記号と同じ4状態である
ウ2状態で十分である
エ1状態だけで判定できる
正解
ウ．2状態で十分である
必要なのは『1の個数が偶数』と『奇数』の区別だけである。初期状態(偶数)から1を読むたびに偶数⇄奇数を切り替えればよく、0は状態を変えない。2状態で十分なので正しい。
?選択肢ごとの解説
ア ×3状態は余分な状態を1つ持つ設計で、偶数・奇数の2区分には不要であり最小ではない。
イ ×4状態は入力記号数(0と1の2種)と状態数を混同した誤りで、判定に必要な区別は2つだけである。
ウ ○必要なのは『1の個数が偶数』と『奇数』の区別だけである。初期状態(偶数)から1を読むたびに偶数⇄奇数を切り替えればよく、0は状態を変えない。2状態で十分なので正しい。
エ ×1状態では偶数と奇数を区別できず、現在のパリティを保持できないため判定不能である。
基礎理論の他の問題
正規表現 ab*c が表す文字列パターンの説明として最も適切なものはどれか。ここで *…BNFで <数字列> ::= <数字> | <数字列><数字> 、<数字> ::= 0|1|2…中置記法の式 (A + B) * C を逆ポーランド記法(後置記法)に変換したものはどれか。次の論理式のうち、PやQの真理値に関わらず常に真となる恒真式(トートロジー)はどれか。4個の要素から成る集合 {a, b, c, d}…ある製品を工場Aが全体の60%、工場Bが40%製造しており、不良率はAが2%、Bが5%である。出荷品から無作為に取った1個が…赤玉3個と白玉5個が入った袋から、玉を1個ずつ続けて2個取り出す。取り出した玉は袋に戻さない。1個目が赤玉であったとき、2個…1個の正しいサイコロを3回振るとき、6の目がちょうど1回だけ出る確率はいくらか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0091