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 where <math>L_1</math> and <math>L_2</math> are defined on the same alphabet Formally:

<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 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> precedes <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.

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 Assuming this is the case, if the split occurs before the first <math>c</math> then <math>0 \le i \le n</math> and , otherwise <math>i=0</math> and 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 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: