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 Template:Nowrap where $L_1$ and $L_2$ are defined on the same alphabet Template:Nowrap Formally:

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

where ${\mathrm{\Sigma }}^{\ast }$ is the Kleene star on $\mathrm{\Sigma }$, $w{L}_2$ is the language formed by concatenating $w$ with each element of Template:Nowrap 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 }}^{\ast }\mid L_{2}w\cap L_1\ne \varnothing \}=\{w\in {\mathrm{\Sigma }}^{\ast }\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$ precedes $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 Template:Nowrap Assuming this is the case, if the split occurs before the first $c$ then $0\le i\le n$ and Template:Nowrap, otherwise $i=0$ and Template:Nowrap 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 Template:Nowrap Template:Nowrap 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 Template:Nowrap there exists $x\in L$ such that Template:No wrap Since then $wx\in L_1$ and Template:Nowrap it must be that Template:Nowrap Conversely, let $w\in L_1/L$ and Template:Nowrap 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 Template:Nowrap 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 Template:Nowrap hence Template:Nowrap

For instance, let $L_1=\{aab,bbb\},$ $L_2=\{abb,bbb\},$ Template:Nowrap

Then Template:No wrap, hence Template:Nowrap

Also $L_1/L=\{a,b\}$ and Template:Nowrap, hence Template:Nowrap

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 Template:Nowrap Then there exists $x\in L_2$ such that Template:Nowrap Therefore, there must exist $y\in L_2^R$ such that Template:Nowrap hence by definition Template:Nowrap It follows that Template:Nowrap and so Template:Nowrap

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