Quotient of a formal language

In mathematics and computer science, 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 prefix of a string $wx$ in $L_{1}$, with the remainder of the word being a string in $L_{2}$.

Similarly, the left quotient of $L_{1}$ with $L_{2}$ is the language consisting of strings w such that xw is in $L_{2}$ for some string x in $L_{1}$. In symbols, we write:

$L_{1}\backslash L_{2}=\{w\ |\ \exists x((x\in L_{1})\land (xw\in L_{2}))\}$

The left quotient can be regarded as the set of postfixes that complete words from $L_{2}$, such that the resulting word is in $L_{1}$.

Example

Consider

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

and

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

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

These closure properties hold for both left and right quotients.

See also

• Brzozowski derivative