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$, where $L_1$ and $L_2$ are defined on the same alphabet $\mathrm{\Sigma }$. Formally:

$$L_1/L_2=\{w\in {\mathrm{\Sigma }}^{*}\mid w{L}_2\cap L_1\ne \varnothing \}=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }x\in L_2:wx\in L_1\}$$

where ${\mathrm{\Sigma }}^{*}$ is the Kleene star on $\mathrm{\Sigma }$, $w{L}_2$ is the language formed by concatenating $w$ with each element of $L_2$, and $\varnothing$ is the empty set.

In other words, for all strings in $L_1$ that have a suffix in $L_2$, the suffix (right part of the string) is removed.

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 L_{2}w\cap L_1\ne \varnothing \}=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }x\in L_2:xw\in L_1\}$$

In other words, for all strings in $L_1$ that have a prefix in $L_2$, the prefix (left part of the string) is removed.

Note that the operands of $\mathrm{\setminus }$ are in reverse order, so that $L_2$ preceeds $L_1$.

The right and left quotients of $L_1$ with respect to $L_2$ may also be written as $L_1{L}_2^{-1}$ and $L_2^{-1}{L}_1$ respectively.

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

If an element of $L_1$ is split into two parts, then the right part will be in $L_2$ if and only if the split occurs somewhere after the final $a$. Assuming this is the case, if the split occurs before the first $c$ then $0\le i\le n$ and $j=n$, otherwise $i=0$ and $0\le j\le n$. For instance:

$aa\mid bbcc(n=2,i=j=2)$

$aaab\mid bbccc(n=3,i=2,j=3)$

$aabbcc\mid ϵ(n=2,i=j=0)$

where $ϵ$ is the empty string.

Thus, the left part will be either $a^n{b}^{n-i}$ or $a^n{b}^n{c}^{n-j}$ $(0\le i,j\le n$), and $L_1/L_2$ can be written as:

$$\{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\}.$$

Basic properties

If $L,L_1,L_2$ are languages over the same alphabet then:

$$(L_1\cup L_2)/L=L_1/L\cup L_2/L$$ $$(L_1\cup L_2)\mathrm{\setminus }L=L_1\mathrm{\setminus }L\cup L_2\mathrm{\setminus }L$$

$$(L_1\cap L_2)/L\subseteq L_1/L\cap L_2/L$$ $$(L_1\cap L_2)\mathrm{\setminus }L\subseteq L_1\mathrm{\setminus }L\cap L_2\mathrm{\setminus }L$$

$$L\mathrm{\setminus }(L_1\cup L_2)=L\mathrm{\setminus }{L}_1\cup L\mathrm{\setminus }{L}_2$$ $$L\mathrm{\setminus }(L_1\cap L_2)\subseteq L\mathrm{\setminus }{L}_1\cap L\mathrm{\setminus }{L}_2$$

$$L_1/L-L_2/L\subseteq (L_1-L_2)/L$$ $$L\mathrm{\setminus }{L}_1-L\mathrm{\setminus }{L}_2\subseteq L\mathrm{\setminus }(L_1-L_2)$$

Example proof

As an example, the third property is proved as follows:

If $w\in (L_1\cap L_2)/L$, there exists $x\in L$ such that $wx\in L_1\cap L_2$. Since then $wx\in L_1$ and $wx\in L_2$, it must be that $w\in L_1/L\cap L_2/L$. Conversely, let $w\in L_1/L$ and $w\in L_2/L$, then there exists $x_1,x_2\in L$ such that $w{x}_1\in L_1$ and $w{x}_2\in L_2$ (given $w$, if $L_1\ne L_2$ then $x_1,x_2$ may differ). Now $w{x}_1\in L_1\cap L_2$ and $w{x}_2\in L_1\cap L_2$ only if $x_1=x_2$, hence $(L_1\cap L_2)/L\subseteq L_1/L\cap L_2/L$.

For instance, let $L_1=\{aab,bbb\},$ $L_2=\{abb,bbb\},$ $L=\{ab,bb\}$.

Then $L_1\cap L_2=\{bbb\}$, hence $(L_1\cap L_2)/L=\{b\}$.

Also $L_1/L=\{a,b\}$ and $L_2/L=\{a,b\}$, hence $L_1/L\cap L_2/L=\{a,b\}$.

Relationship between right and left quotients

The right and left quotients of languages $L_1$ and $L_2$ are related through the language reversals $L_1^R$ and $L_2^R$ by the equalities:

$$L_1/L_2=(L_2^R\mathrm{\setminus }{L}_1^R{)}^R$$ $$L_2\mathrm{\setminus }{L}_1=(L_1^R/L_2^R{)}^R$$

Proof

To prove the first equality, let $w\in L_1/L_2$. Then there exists $x\in L_2$ such that $wx\in L_1$. Therefore, there must exist $y\in L_2^R$ such that $y{w}^R\in L_1^R$, hence by definition $w^R\in L_2^R\mathrm{\setminus }{L}_1^R$. It follows that $w\in (L_2^R\mathrm{\setminus }{L}_1^R{)}^R$, and so $L_1/L_2=(L_2^R\mathrm{\setminus }{L}_1^R{)}^R$.

The second equality is proved in a similar manner.

Other 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