基本情報技術者試験「BNF」の問題
BNFで <数字列> ::= <数字> | <数字列><数字> 、<数字> ::= 0|1|2 と定義されている。この規則が生成する文字列として正しいものはどれか。
ア201 は規則に従って生成できる
イ3 は生成できる正しい文字列である
ウ空文字列(長さ0)も生成される
エ−12 のように符号付きでも生成できる
正解
ア．201 は規則に従って生成できる
<数字>は0|1|2のいずれか1文字。<数字列>は<数字>単独、または<数字列>の後ろに<数字>を1つ付ける再帰で、0〜2の数字を1個以上並べた列を生成する。201は2,0,1がすべて該当し生成可能なので正しい。
?選択肢ごとの解説
ア ○<数字>は0|1|2のいずれか1文字。<数字列>は<数字>単独、または<数字列>の後ろに<数字>を1つ付ける再帰で、0〜2の数字を1個以上並べた列を生成する。201は2,0,1がすべて該当し生成可能なので正しい。
イ ×3は<数字>の定義(0|1|2)に含まれないため、どの規則でも生成できない。
ウ ×<数字列>は最低でも<数字>1個から始まる定義で空文字列を導く規則がないため、長さ0は生成されない。
エ ×符号−を生成する規則は定義に存在しないため、−12のような符号付き文字列は生成できない。
✎くわしく
BNFの::=は定義、|は選択肢、再帰的定義<数字列>::=<数字列><数字>は『繰返し』を表す。生成可能か否かは『定義に現れる終端記号と規則だけで導けるか』で判定する。定義にない記号(3や−)は決して生成されない点が核心である。
✓本番での押さえどころ
試験のコツ
BNFは『定義された終端記号だけ』『規則の通りにしか』生成されない。選択肢の各文字が定義に含まれるか1文字ずつ照合する。
覚え方
BNFは『レシピ』。レシピに載っていない材料(3や符号)は決して料理に入らない、と覚える。
よくある誤り
定義に無い終端記号を含む文字列を生成可能と誤判定する、または再帰規則を見落として1文字しか作れないと誤解する。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0093