制作（コンピュータサイエンス）

Method of symbol substitution

コンピュータサイエンスにおいて、生成規則または生成ルールとは、ある記号を他の記号に置き換える書き換え規則のことである。 ^[1]有限集合の生成ルールは、形式文法（特に生成文法）の仕様における主要な構成要素である。 ${\displaystyle P}$

このような文法では、生成規則の集合は、文字列の集合（ここではクリーネのスター演算子）上の関係の特別なケースであり、語彙と呼ばれる有限の記号集合は、どの空でない文字列が他の文字列に置き換えられるかを定義する。したがって、生成規則の集合は特別な種類の部分集合である。 ${\displaystyle V^{*}}$ ${\displaystyle {}^{*}}$ ${\displaystyle V}$

${\displaystyle P\subset V^{*}\times V^{*}}$

そして、生成規則は という形式で書かれ、という意味になります（関数表記法として使用されるものと混同しないでください。同じ に対して複数の規則が存在する場合があるためです）。2つの部分集合 が与えられた場合、生成規則は を満たすように制限することができ、その場合、生成規則は「 という形式である」と言われます。 の選択や構成が異なると、文法の種類も異なります。一般に、 という形式の生成規則はどれも ${\displaystyle u\to v}$ ${\displaystyle (u,v)\in P}$ ${\displaystyle \to }$ ${\displaystyle u}$ ${\displaystyle A,B\subset V^{*}}$ ${\displaystyle P\subset A\times B}$ ${\displaystyle A\to B}$ ${\displaystyle A,B}$

${\displaystyle u\to \epsilon ,}$

ここでは空文字列（ と表記されることもある）であるが、これは消去規則と呼ばれる。一方、どこからともなく文字列を生成する生成規則、すなわち次のような形式は、 ${\displaystyle \epsilon }$ ${\displaystyle \lambda }$

${\displaystyle \epsilon \to v,}$

決して許可されません。

生成規則が意味のある文を作成できるようにするために、語彙は（互いに素な）セットに分割され、2 つの異なる役割が提供されます。 ${\displaystyle \Sigma }$ ${\displaystyle N}$

• ${\displaystyle \Sigma }$文中で使用できる記号を含むアルファベットと呼ばれる終端記号を表します。
• ${\displaystyle N}$は、文の構築方法を定義するために生成規則とともに必要な、区別される開始記号を含む非終端記号を表します。 ${\displaystyle S\in N}$

無制限文法の最も一般的なケースでは、生成規則 は、 が空でない限り、任意の文字列と を（終端記号と非終端記号）にマッピングすることが許される。したがって、無制限文法には以下の形式の生成規則が存在する。 ${\displaystyle u\to v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle V}$ ${\displaystyle u}$

${\displaystyle V^{*}\setminus \{\epsilon \}\to V^{*}}$

あるいは、完成した文の変更を禁止したい場合

${\displaystyle V^{*}NV^{*}=(V^{*}\setminus \Sigma ^{*})\to V^{*}}$、

ここで、は連結を示し、生成規則の左側に非終端記号が常に存在することを強制します。は和集合、は差集合または差集合を表します。開始記号が（右側の単語）に出現することを許可しない場合は、右側をに置き換える必要があります。 ^[2] ${\displaystyle V^{*}NV^{*}}$ ${\displaystyle \cup }$ ${\displaystyle \setminus }$ ${\displaystyle v}$ ${\displaystyle V^{*}}$ ${\displaystyle (V\setminus \{S\})^{*}}$

チョムスキー階層の他の種類の形式文法は、生成規則の構成要素にさらなる制約を課します。特に文脈自由文法では、生成規則の左辺は単一の非終端記号でなければなりません。したがって、生成規則は以下の形式となります。

${\displaystyle N\to V^{*}}$

文法生成

この言語で文字列を生成するには、まず開始記号1 個のみからなる文字列を作成し、次に規則を（任意の回数、任意の順序で）適用してこの文字列を書き換えます。この処理は、終端記号のみからなる文字列が得られたときに停止します。この言語は、このように生成できるすべての文字列で構成されています。この書き換えプロセス中に行われる有効な選択の特定のシーケンスは、言語において特定の文字列を生成します。この単一の文字列を生成する方法が複数存在する場合、その文法は曖昧であると言われます。

たとえば、アルファベットが と で構成され、開始記号が で、次の規則があるとします。 ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle S}$

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

から始めて、それに適用する規則を選択できます。規則 1 を選択した場合は、を に置き換えて文字列 を取得します。規則 1 をもう一度選択すると、を に置き換えて文字列 を取得します。このプロセスは、アルファベットの記号 (つまり、と) だけになるまで繰り返されます。ここで規則 2 を選択すると、を に置き換えて文字列 を取得し、これで完了です。この一連の選択は、記号を使用して、より簡潔に記述できます。文法の言語は、このプロセスを使用して生成できるすべての文字列の集合です。 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle aSb}$ ${\displaystyle aSb}$ ${\displaystyle S}$ ${\displaystyle aSb}$ ${\displaystyle aaSbb}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle ba}$ ${\displaystyle aababb}$ ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$ ${\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}$

参照

• 正式な文法
• 有限オートマトン
• 生成文法
• Lシステム
• 書き換えルール
• バッカス・ナウア形式（文脈自由文法の生成物を記述するためのコンパクトな形式）
• フレーズ構造のルール
• ポスト標準システム(エミール・ポストの生成システム - 計算モデル)

参考文献

1. 「形式文法」（PDF）Standford.edu。
2. Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronization von Halbspurspra​​chen を参照。2018 年 1 月 17 日にウェイバック マシンにアーカイブ。シュトゥットガルト大学情報学部; 1994年 (ドイツ語)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Production_(computer_science)&oldid=1319651885"