# Right quotient

The right quotient (or simply quotient) of a formal language ${\displaystyle L_{1}}$ with a formal language ${\displaystyle L_{2}}$ is the language consisting of strings w such that wx is in ${\displaystyle L_{1}}$ for some string x in ${\displaystyle L_{2}}$.[1] In symbols, we write:

${\displaystyle L_{1}/L_{2}=\{w\ |\ \exists x((x\in L_{2})\land (wx\in L_{1}))\}}$

In other words, each string in ${\displaystyle L_{1}/L_{2}}$ is the prefix of a string ${\displaystyle wx}$ in ${\displaystyle L_{1}}$, with the remainder of the word being a string in ${\displaystyle L_{2}}$.

## Example

Consider

${\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\ \ |\ \ n\geq 0\}}$

and

${\displaystyle L_{2}=\{b^{i}c^{j}\ \ |\ \ i,j\geq 0\}}$.

Now, if we insert a divider into the middle of an element of ${\displaystyle L_{1}}$, the part on the right is in ${\displaystyle L_{2}}$ only if the divider is placed adjacent to a b (in which case i ≤ n and j = n) or adjacent to a c (in which case i = 0 and j ≤ n). The part on the left, therefore, will be either ${\displaystyle a^{n}b^{n-i}}$ or ${\displaystyle a^{n}b^{n}c^{n-j}}$; and ${\displaystyle L_{1}/L_{2}}$ can be written as

${\displaystyle \{a^{p}b^{q}c^{r}\ \ |\ \ p=q\geq r\ \ \lor \ \ p\geq q\land r=0\}}$.

## Properties

Some common closure properties of the right quotient 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.

## Left and right quotients

There is a related notion of left quotient, which keeps the postfixes of ${\displaystyle L_{1}}$ without the prefixes in ${\displaystyle L_{2}}$. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.

## References

1. ^ Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Retrieved 7 July 2014.