正規文法とは

以下のような置き換えで定義される.

• W -> aW, W -> a (W: 非終端記号、a: 終端記号、ε: 非終端記号の終了)

表現を簡略化するためにW -> εも許される。

例

奇数個のaを含む文字列のみ生成する正規文法

• Sから開始
• S -> aT|bS
• T -> aS|bT|ε (S, T: 非終端記号、a, b: 終端記号、ε: 非終端記号の終了, |: or)

対応するオートマトン

有限状態オートマトン

使用例

• DNAの繰り返し配列の判定

DNAの配列を1文字ずつ受け取り、最後に終端記号ならば繰り返し配列だと判定可能なオートマトンが定義できる。

• 従来のBLAST

• ムーア機械とミーリー機械

ミーリー機械: 記号を受理する有限状態オートマトン

ムーア機械: 状態を受理する有限状態オートマトン

これらは互いに変換可能。

• 決定性オートマトンと非決定性オートマトン

決定性オートマトン:

遷移（入力を受け取る順番）が一種類しかないため線形時間で処理が可能。

非決定性オートマトン:

複数の繊維の組み合わせを許す。計算時間が発散する。

決定性オートマトンに変換可能 -> 簡略な非決定性オートマトンによるモデルを定義した後、決定性オートマトンに変換して線形時間で計算可能

正規文法で出来ないこと

正規文法だけで回文だけを発生させることができない。つまり正しい回文と回分でないものを区別することができない

複写（同一の２個の部分からなる文字列 例: aabaab）も同様 -> 右側に終端記号を並べられないため

文脈自由文法とは

正規文法では回文が生成できないように、入れ子構造の終端記号の遠距離の相互作用を許さない。 それを実現するために、正規文法に追加して、任意の非終端記号Sと終端記号aの組み合わせを許す。(一方、左辺は正規文法と同様に「一個の非終端記号S」に限られる)

例

正規文法と異なり回文を生成可能な例

S -> aSb|bSb|aa|bb

このsによる回文aabaabaaの導出

s→asa→aasaa→aabsbaa→aabaabaa

生物学との関連

RNAステムループ構造の判定に使える。(問題参照)

構文解析木による表現

以下のように構文解析木で表現すると、文脈自由文法により離れたところの依存関係を表現できることがわかる。

実装

スタックを用いる