Quotient of a formal language
In mathematics and computer science, the right quotient (or simply quotient) of a language <math>L_1</math> with respect to language <math>L_2</math> is the language consisting of strings <math>w</math> such that <math>wx</math> is in <math>L_1</math> for some string <math>x</math> in Template:Nowrap where <math>L_1</math> and <math>L_2</math> are defined on the same alphabet Template:Nowrap Formally:<ref name="Pin">Template:Cite book</ref><ref name="Linz">Template:Cite book (Fifth ed. at Google Books)</ref>
<math display="block">L_1 / L_2 = \{w \in \Sigma^* \mid wL_2 \cap L_1 \neq \varnothing\} = \{w \in \Sigma^* \mid \exists x \in L_2 \ \colon\ wx \in L_1\}</math>
where <math>\Sigma^*</math> is the Kleene star on <math>\Sigma</math>, <math>wL_2</math> is the language formed by concatenating <math>w</math> with each element of Template:Nowrap and <math>\varnothing</math> is the empty set.
In other words, for all strings in <math>L_1</math> that have a suffix in <math>L_2</math>, the suffix (right part of the string) is removed.
Similarly, the left quotient of <math>L_1</math> with respect to <math>L_2</math> is the language consisting of strings <math>w</math> such that <math>xw</math> is in <math>L_1</math> for some string <math>x</math> in <math>L_2</math>. Formally:
<math display="block">L_2 \backslash L_1 = \{w \in \Sigma^* \mid L_2w \cap L_1 \neq \varnothing\} = \{w \in \Sigma^* \mid \exists x\in L_2 \ \colon\ xw \in L_1\}</math>
In other words, for all strings in <math>L_1</math> that have a prefix in <math>L_2</math>, the prefix (left part of the string) is removed.
Note that the operands of <math>\backslash</math> are in reverse order, so that <math>L_2</math> preceeds <math>L_1</math>.
The right and left quotients of <math>L_1</math> with respect to <math>L_2</math> may also be written as <math>L_1 L_2^{-1}</math> and <math>L_2^{-1} L_1</math> respectively.<ref name="Pin"/><ref name="Simovici">Template:Cite book</ref>
Example
Consider <math display="block">L_1 = \{ a^n b^n c^n \mid n \ge 0 \}</math> and <math display="block">L_2 = \{ b^i c^j \mid i,j \ge 0 \}.</math>
If an element of <math>L_1</math> is split into two parts, then the right part will be in <math>L_2</math> if and only if the split occurs somewhere after the final Template:Nowrap Assuming this is the case, if the split occurs before the first <math>c</math> then <math>0 \le i \le n</math> and Template:Nowrap, otherwise <math>i=0</math> and Template:Nowrap For instance:
<math>aa \mid bbcc \ \ (n=2, i=j=2)</math>
<math>aaab \mid bbccc \ \ (n=3, i=2, j=3)</math>
<math>aabbcc \mid \epsilon \ \ (n=2, i=j=0)</math>
where <math>\epsilon</math> is the empty string.
Thus, the left part will be either <math>a^n b^{n-i}</math> or Template:Nowrap Template:Nowrap and <math>L_1 / L_2</math> can be written as:
<math display="block">\{\ a^p b^q c^r \ \mid\ (p \ge q \text{ and } r = 0) \ \ \text{or} \ \ p = q \ge r \ \ ; \ \ p, q, r \ge 0 \ \}.</math>
Basic properties
If <math>L, L_1, L_2</math> are languages over the same alphabet then:<ref name="Simovici"/>
<math display="block">(L_1 \cup L_2) / L \ = \ L_1 / L \ \cup \ L_2 / L</math> <math display="block">(L_1 \cup L_2) \backslash L \ = \ L_1 \backslash L \ \cup \ L_2 \backslash L</math>
<math display="block">(L_1 \cap L_2) / L \ \subseteq \ L_1 / L \ \cap \ L_2 / L</math> <math display="block">(L_1 \cap L_2) \backslash L \ \subseteq \ L_1 \backslash L \ \cap \ L_2 \backslash L</math>
<math display="block">L \backslash (L_1 \cup L_2) \ = \ L \backslash L_1 \ \cup \ L \backslash L_2</math> <math display="block">L \backslash (L_1 \cap L_2) \ \subseteq \ L \backslash L_1 \ \cap \ L \backslash L_2</math>
<math display="block">L_1 / L - L_2 / L \ \subseteq \ (L_1 - L_2) / L</math> <math display="block">L \backslash L_1 - L \backslash L_2 \ \subseteq \ L \backslash (L_1 - L_2) </math>
Example proof
As an example, the third property is proved as follows:
If Template:Nowrap there exists <math>x \in L</math> such that Template:No wrap Since then <math>wx \in L_1</math> and Template:Nowrap it must be that Template:Nowrap Conversely, let <math>w \in L_1 / L</math> and Template:Nowrap then there exists <math>x_1, x_2 \in L</math> such that <math>wx_1 \in L_1</math> and <math>wx_2 \in L_2</math> (given Template:Nowrap if <math>L_1 \neq L_2</math> then <math>x_1,x_2</math> may differ). Now <math>wx_1 \in L_1 \cap \ L_2</math> and <math>wx_2 \in L_1 \cap \ L_2</math> only if Template:Nowrap hence Template:Nowrap
For instance, let <math>L_1 = \{aab, bbb\},</math> <math>L_2 = \{abb, bbb\},</math> Template:Nowrap
Then Template:No wrap, hence Template:Nowrap
Also <math>L_1 / L = \{a, b\}</math> and Template:Nowrap, hence Template:Nowrap
Relationship between right and left quotients
The right and left quotients of languages <math>L_1</math> and <math>L_2</math> are related through the language reversals <math>L_1^R</math> and <math>L_2^R</math> by the equalities:<ref name="Simovici"/>
<math display="block">L_1 / L_2 = (L_2^R \backslash L_1^R)^R</math> <math display="block">L_2 \backslash L_1 = (L_1^R / L_2^R)^R</math>
Proof
To prove the first equality, let Template:Nowrap Then there exists <math>x \in L_2</math> such that Template:Nowrap Therefore, there must exist <math>y \in L_2^R</math> such that Template:Nowrap hence by definition Template:Nowrap It follows that Template:Nowrap and so Template:Nowrap
The second equality is proved in a similar manner.
Other properties
Some common closure properties of the quotient operation include:
- The quotient of a regular language with any other language is regular.
- The quotient of a context free language with a regular language is context free.
- The quotient of two context free languages can be any recursively enumerable language.
- The quotient of two recursively enumerable languages is recursively enumerable.
These closure properties hold for both left and right quotients.