変形文法（生成文法）

変形文法の概要

文章を生成するから生成文法とも呼ばれる。

チョムスキーにより提唱された、「文章が文法的に正しいかどうか判断」「構文解析」するアルゴリズム（形式機械）。

言語の制約を少ない規則で再現することを目的にしている。

正規文法を確率化した隠れマルコフモデルはDNA配列のアラインメントなどに有用文脈自由文法を確率化した確率文脈自由文法はRNAの構造解析などに有用

「記号」と「記号から記号への置き換え規則」から成る。記号は「非終端記号」（実際の文章には現れない抽象的なものを仮定。書き換えられる。）と「終端記号」（文章として現れる記号。文字や単語、音節。書き換えられない。）から成る。

(S: 非終端記号、a,b: 終端記号、ε: 非終端記号の終了)

この規則に従えば全ての組み合わせのaとbから成る文字列を生成可能。

S -> aS, S -> a (S: 非終端記号、a: 終端記号)

S -> 任意のS, aの組み合わせ (S: 非終端記号、a: 終端記号)

上記の文法の遷移に確情情報を付加。