正規表現や BNF はコンパイラ・パーサ・ログ解析・ネットワーク機器の設定など、ITエンジニアの日常で必ず使う道具です。
鳴海 理央
形式言語 は文法で厳密に定義された言語のこと。
オートマトン は状態と遷移で計算を表現するモデルで、有限オートマトン は 正規表現 と等価です。
砂原 ニコ
正規表現?
あの \d+ とかのやつ?
緒方 ナオミ 先生
そう。
AP では『この正規表現にマッチする文字列はどれか』『このオートマトンが受理する言語はどれか』が問われるわ。
藤咲 まりあ
BNF って何ですかぁ?
鳴海 理央
Backus-Naur Form。
文脈自由文法を ::= で記述する記法です。
たとえば <数字>::=0|1|2|...|9 のように、構文を再帰的に定義できます。
プログラミング言語の仕様書はだいたい BNF 派生で書かれます。
緒方 ナオミ 先生
チューリングマシン は計算可能性の限界を定義する数学モデル。
AP では『有限オートマトン < プッシュダウンオートマトン < チューリングマシン』の階層があることを覚えておけば十分。
有限オートマトンを一文字ずつ追跡する
「0と1からなる文字列で、最後が01なら受理する」オートマトンを考えます。状態S0を「末尾に手掛かりなし」、S1を「末尾が0」、S2を「末尾が01で受理」とします。入力1101なら、S0から1でS0、次の1でもS0、0でS1、最後の1でS2へ進むため受理されます。入力を読み終えた時点の状態が受理状態かどうかが答えであり、途中で一度受理状態を通っただけでは不十分です。
状態遷移表の問題では、現在状態を左端に書き、入力を左から一文字ずつ消しながら次状態へ更新します。正規表現なら同じ言語を (0|1)*01 と表せます。* は直前の要素を0回以上、+ は1回以上、? は0回または1回繰り返す演算子です。「任意の1文字」を表すピリオドと、文字としてのピリオドを混同しない点にも注意します。
正規表現・BNF・計算モデルを選び分ける
| 表したい対象 | 適した記法・モデル | 具体例 |
|---|---|---|
| 有限状態で判定できる文字列 | 正規表現／有限オートマトン | 識別子、郵便番号の形式 |
| 入れ子を含む構文 | BNF／文脈自由文法 | 括弧式、プログラムの構文 |
| 一般のアルゴリズム | チューリングマシン | 計算可能性の議論 |
BNFの再帰は、停止できる基底規則と、より長い形を作る再帰規則に分けて読みます。<数> ::= <数字> | <数><数字> では前半が1桁を作る基底、後半が末尾へ1桁追加する再帰です。典型誤答は再帰規則だけを見て「必ず2桁以上」と判断することです。また、有限オートマトンは状態を増やせても、対応する個数の開き括弧と閉じ括弧のような無制限の入れ子は記憶できません。この性質から、入れ子構文にはBNFを選びます。
確認クイズ
BNF で定義された次の文法 <数> ::= <数> <数字> | <数字> について、正しい説明はどれか。
- 1桁の数字のみを表す
- 1桁以上の数字列を表す
- 必ず2桁以上の数字列を表す
- 符号付き整数を表す
こたえを見る
正解: 2. 1桁以上の数字列を表す
<数字> 単独でも <数> になるため1桁を表せ、再帰的に <数> <数字> でいくらでも長い数字列が作れるため、1桁以上の数字列を表します。BNF の再帰定義の典型例です。