形式文法

文法 grammer

有限個の規則のことを文法(grammer)といいます.

形式言語の文法は,終端記号の集合 $T$(Terminal symbol) ,非終端記号の集合 $N$(Non-terminal symbol),生成規則の集合 $P$(Production rule),開始記号 $S$(Start symbol) によって定義されます.

形式文法の4要素

終端記号$T$これ以上置き換えの起こらない要素を表現する最小単位の記号のこと.
自然言語である英語や日本語における単語などが終端記号に相当します.
非終端記号$N$文を作成する途中にだけ現れる概念を表す記号のこと.
自然言語である英語や日本語においては「文」「動詞」「主語」「目的語」「名詞」などが非終端記号に相当します.
生成規則$P$文において,記号列を置き換える規則のこと.
開始記号$S$各形式文法について1つ定められる,形式文法によって生成される記号列の始まりを表す記号のこと..

形式文法の定義

形式文法 $G$ は,\[G=(N,T,P,S)\]と表されます.

なお,\[N \cap T = \emptyset\]つまり,非終端記号 $N$ と,終端記号 $T$ は共通の記号を含みません.

Vita brevis, ars longa. Omnia vincit Amor.





















C*環 真偽値表/真理値表 有限オートマトンの多様体 正規言語(regular lamguage) セルオートマトン 真偽値の領域