Right quotient

The right quotient (or simply quotient) of a formal language $L\_1$ with a formal language $L\_2$ is the language consisting of strings "w" such that "wx" is in $L\_1$ for some string "x" in $L\_2$. In symbols, we write:

:$L\_1\; /\; L\_2\; =\; \{w\; |\; exists\; x\; ((x\; in\; L\_2)\; land\; (wx\; in\; L\_1))\; \}$

In other words, each string in $L\_1\; /\; L\_2$ is the first part of a string in $L\_1$, with the rest being a string in $L\_2$.

Examples

Consider $L\_1\; =\; \{\; a^n\; b^n\; c^n\; \}$ and $L\_2\; =\; \{\; b^i\; c^j\; \}$ (where "n", "i", and "j" are nonnegative integers). Now, if we insert a divider into the middle of an element of $L\_1$, the part on the right is in $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 $a^n\; b^\{n-i\}$ or $a^n\; b^n\; c^\{n-j\}$; and $L\_1\; /\; L\_2$ can be written as $\{\; a^p\; b^q\; c^r\; |\; p\; =\; q\; ge\; r\; or\; p\; ge\; q\; and\; 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 $L\_1$ without the prefixes in $L\_2$. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.