基本情報技術者 予想問題｜A 第22問

解説

正解はイ。有限オートマトンは、状態と入力による状態遷移で文字列を受理するかどうかを判定する計算モデルである。決定性有限オートマトン（DFA）では、ある状態と入力に対して遷移先が常に1つに定まる。一方、非決定性有限オートマトン（NFA）では、遷移先が複数あったり、入力なしで遷移するε遷移を許したりする。一見NFAの方が表現力が高そうに見えるが、NFAの「とり得る状態の集合」をDFAの1つの状態とみなす部分集合構成法により、任意のNFAは等価なDFAに変換できることが証明されている。したがって両者が受理できる言語のクラスはどちらも正規言語で一致し、ア・ウ・エの「受理できる言語が異なる・NFAの方が多い・変換できない」はいずれも誤りである。基本情報では、状態遷移図から受理される文字列を判定する問題が頻出である。