Production (computer science) とは

コンピュータサイエンスの生産ルールまたは生産ルールは、新しいシンボルシーケンスを生成するために再帰的に実行できるシンボル置換を指定する書き換えルールです。有限集合の生成 P {\displaystyle P} は、形式的文法(特に生成文法)の仕様における主要な構成要素である。他の構成要素は、非終端記号の有限集合 N {\displaystyle N} N {\displaystyle N} から離れた終端記号の有限集合(アルファベットと呼ばれる) Σ {\displaystyle \Sigma } 、開始記号である識別記号 S N {\displaystyle S\in N} である。
無制限の文法では、生産は u {\displaystyle u} v {\displaystyle v} は任意の文字列の端末と非終端記号ですが、 u {\displaystyle u} は空の文字列ではありません。 v {\displaystyle v} が空文字列の場合、これは ϵ {\displaystyle \epsilon } または λ {\displaystyle \lambda } という記号で表示されます(右側を空白にするのではなく)。したがって、プロダクションはデカルト積のメンバーです
V N V × V = ( V Σ ) × V {\displaystyle V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}}
ここで V := N Σ {\displaystyle V:=N\cup \Sigma } はボキャブラリ、 {\displaystyle {}^{*}} はクレーネ星の演算子、 V N V {\displaystyle V^{*}NV^{*}} は連結を表し、 {\displaystyle \cup } は組合を表す。開始記号が v {\displaystyle v} (右側の単語)に出現しないようにするには、デカルト積記号の右側の V {\displaystyle V^{*}} ( V { S } ) {\displaystyle (V\setminus \{S\})^{*}} で置き換えなければなりません。
チョムスキー階層の他のタイプの形式的文法は、生産を構成するものに追加の制限を課す。特に文脈自由文法では、プロダクションの左辺は単一の非終端記号でなければなりません。したがって、制作は次のような形になります。
N ( N Σ ) {\displaystyle N\to (N\cup \Sigma )^{*}}