基礎理論

BNF（バッカス・ナウア記法）で次のように定義された <数> が表すものとして、正しい例はどれか。 <数> ::= <数字> | <数字> <数> <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

ア.+123

イ.12.5

ウ.2026正解

エ.0x1F

解説

BNF の再帰定義「数 = 数字または数字+数」は、要するに「1桁以上の数字の並び」を表す——電卓に表示できる整数列のイメージです。

なぜウが正解か

<数> は「<数字> 1つ」または「<数字> の後ろにさらに <数> が続く」と再帰的に定義されており、結果として「1桁以上の数字の連なり」を生成します。2026 はすべて 0〜9 の数字だけで構成された4桁の整数なので、この文法でちゃんと導出可能。よってウが正解です。

なぜアは間違いか

+123 の先頭の「+」は <数字> にも <数> にも含まれていない記号。文法に許可がない以上、この入力は受理されません。

なぜイは間違いか

12.5 にある「.」（小数点）は定義に存在しない記号です。BNF で扱える文字は <数字> として列挙された 0〜9 だけで、句読点を勝手に持ち込めません。

なぜエは間違いか

0x1F の「x」「F」は <数字>（0〜9）に含まれない英字。16進表記を BNF に拡張するには別ルールが必要で、この定義のままでは受理不能です。

出典: AI生成問題（学習用）

← 前の問題

有限オートマトンに関する記述として、最も適切なものはどれか。

次の問題 →

2進数の加算 1011 + 0110 の結果を10進数で表したものはどれか。