Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language $L_1$ with respect to language $L_2$ is the language consisting of strings w such that wx is in $L_1$ for some string x in $L_2$. Formally: $$L_1/L_2=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }x\in L_2:wx\in L_1\}$$

In other words, we take all the strings in $L_1$ that have a suffix in $L_2$, and remove this suffix.

Similarly, the left quotient of $L_1$ with respect to $L_2$ is the language consisting of strings w such that xw is in $L_1$ for some string x in $L_2$. Formally: $$L_2\mathrm{\setminus }{L}_1=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }x\in L_2:xw\in L_1\}$$

In other words, we take all the strings in $L_1$ that have a prefix in $L_2$, and remove this prefix.

Note that the operands of $\mathrm{\setminus }$ are in reverse order: the first operand is $L_2$ and $L_1$ is second.

Example

Consider $$L_1=\{a^n{b}^n{c}^n\mid n\ge 0\}$$ and $$L_2=\{b^i{c}^j\mid i,j\ge 0\}.$$

Now, if we insert a divider into 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\mid p=q\ge r\text{or}(p\ge q\text{ and }r=0)\}.$$

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.

See also

• Brzozowski derivative