文脈自由文法

文脈自由文法(CFG)の定義

形式文法 $G=(N,T,P,S)$ における生成規則 $P$ が以下で表されるとき,その形式文法 $G$ は文脈自由文法(Context-free Grammar,CFG)といいます.\[A \to \alpha,\alpha \in (N \cup T)\]ここで,終端記号の集合 $T$(Terminal symbol) ,非終端記号の集合 $N$(Non-terminal symbol),生成規則の集合 $P$(Production rule),開始記号 $S$(Start symbol) です.

文脈自由文法の標準形

自由文脈文法では様々な形式の生成規則 $P$ を定義することが可能です.

これではコンピュータで扱う際に不便なので,一定の標準的な形式で文脈自由文法の生成規則 $P$ を表現しようというのが,文脈自由文法の標準形の考え方です.

この標準形には,どのような文脈自由文法の生成規則 $P$ でも標準形の生成規則に変換することができるということが求められます.このような条件を満たす文脈自由文法の標準形として以下の2つの標準形が知られています.

チョムスキー標準形(CNF;Chomsky Normal Form)正規文法の生成規則のうち終端記号と1つの非終端記号の組み合わせを2つの非終端記号へと変更したもの.
グライバッハ標準形(GNF;Greibach Normal Form)左端に1個の終端記号と0個以上の非終端記号を生成するという生成規則をもつもの.

チョムスキー標準形(CNF;Chomsky Normal Form)

文脈自由文法 $G=(N,T,P,S)$ における生成規則 $P$ の全てが以下のいずれかの形式であるとき,$G$ はチョムスキー標準形(CNF)といいます.

チョムスキー標準形(CNF)という名前は,米国の言語学者エイヴラム・ノーム・チョムスキー(Avram Noam Chomsky,1928年12月7日-)にちなむものです.\[S \to \varepsilon\tag{1}\]\[A \to a\tag{2}\]\[A \to BC\tag{3}\]ここで,\[\forall A \forall B \forall C \in N\]\[\forall a \in T\]そして,$\varepsilon$ は空記号列です.

グライバッハ標準形(GNF;Greibach Normal Form)

文脈自由文法 $G=(N,T,P,S)$ における生成規則 $P$ の全てが以下のいずれかの形式であるとき,$G$ はグライバッハ標準形(GNF)といいます.

グライバッハ標準形(GNF)という名前は,米国の計算機科学者シーラ・グライバッハ(Sheila Adele Greibach,1939年10月6日-)にちなむものです.\[S \to \varepsilon\tag{1}\]\[A \to a\tag{2}\]\[A \to aB_{1}B_{2}\cdots B_{m}\tag{3}\]ここで,\[\forall A \forall B_{1}\forall B_{2}\cdots\forall B_{m} \in N\]\[\forall a \in T\]そして,$\varepsilon$ は空記号列です.

Vita brevis, ars longa. Omnia vincit Amor.





















濃度 同値関係と商集合 正規文法 形式文法と有限オートマトン 文と言語と文法 ゾゾウスキ導分(Brzozowski derivative)