形式言語の商

数学とコンピュータサイエンスにおいて、言語の言語に対する右商（または単に商）とは、ある文字列xに対してwxが成立するような文字列wで構成される言語のことである。^[1]正式には： ${\displaystyle L_{1}}$${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$${\displaystyle L_{2}}$$${\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}}$$

つまり、にサフィックスがあるのすべての文字列について、サフィックスが削除されます。 ${\displaystyle L_{1}}$${\displaystyle L_{2}}$

同様に、に関するの左商は、内の何らかの文字列xに対してxw がとなるような文字列wで構成される言語です。正式には、 ${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$$${\displaystyle L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ xw\in L_{1}\}}$$

つまり、内のプレフィックスを持つ内のすべての文字列を取得し、このプレフィックスを削除します。 ${\displaystyle L_{1}}$${\displaystyle L_{2}}$

のオペランドは逆の順序になっていることに注意してください。最初のオペランドは で、は 2 番目です。 ${\displaystyle \backslash}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$

考慮し て $${\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$$$${\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}$$

ここで、 の要素に分周器を挿入すると、分周器が a bに隣接している場合（この場合i  ≤  nかつj  =  n）、または a cに隣接している場合（この場合i  = 0 かつj  ≤  n）にのみ、右側の部分が になります。したがって、左側の部分はまたは のいずれかになり、次のように記述できます 。${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle a^{n}b^{ni}}$${\displaystyle a^{n}b^{n}c^{nj}}$${\displaystyle L_{1}/L_{2}}$$${\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{または}}\ \ (p\geq q{\text{かつ}}r=0)\ \}.}$$

商演算の一般的な閉包特性には次のものがあります。

• 正規言語と他の言語の商は正規です。
• 文脈自由言語と正規言語の商は文脈自由です。
• 2 つの文脈自由言語の商は、任意の再帰的に列挙可能な言語になります。
• 2 つの再帰的に列挙可能な言語の商は再帰的に列挙可能です。

これらの閉包特性は左商と右商の両方に当てはまります。

• ブロゾフスキー微分