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 $\Sigma$. Formally:

$$L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid wL_{2}\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ wx\in L_{1}\}$$

where $\Sigma ^{*}$ is the Kleene star on $\Sigma$, $wL_{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}\backslash L_{1}=\{w\in \Sigma ^{*}\mid L_{2}w\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ 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 $\backslash$ 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\geq 0\}$$ and $$L_{2}=\{b^{i}c^{j}\mid i,j\geq 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\leq i\leq n$ and $j=n$, otherwise $i=0$ and $0\leq j\leq n$. For instance:

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

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

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

where $\epsilon$ 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\leq i,j\leq n$), and $L_{1}/L_{2}$ can be written as:

$$\{\ a^{p}b^{q}c^{r}\ \mid \ (p\geq q{\text{ and }}r=0)\ \ {\text{or}}\ \ p=q\geq r\ \ ;\ \ p,q,r\geq 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})\backslash L\ =\ L_{1}\backslash L\ \cup \ L_{2}\backslash L$$

$$(L_{1}\cap L_{2})/L\ \subseteq \ L_{1}/L\ \cap \ L_{2}/L$$ $$(L_{1}\cap L_{2})\backslash L\ \subseteq \ L_{1}\backslash L\ \cap \ L_{2}\backslash L$$

$$L\backslash (L_{1}\cup L_{2})\ =\ L\backslash L_{1}\ \cup \ L\backslash L_{2}$$ $$L\backslash (L_{1}\cap L_{2})\ \subseteq \ L\backslash L_{1}\ \cap \ L\backslash L_{2}$$

$$L_{1}/L-L_{2}/L\ \subseteq \ (L_{1}-L_{2})/L$$ $$L\backslash L_{1}-L\backslash L_{2}\ \subseteq \ L\backslash (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 $wx_{1}\in L_{1}$ and $wx_{2}\in L_{2}$ (given $w$, if $L_{1}\neq L_{2}$ then $x_{1},x_{2}$ may differ). Now $wx_{1}\in L_{1}\cap \ L_{2}$ and $wx_{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}\backslash L_{1}^{R})^{R}$$ $$L_{2}\backslash 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 $yw^{R}\in L_{1}^{R}$, hence by definition $w^{R}\in L_{2}^{R}\backslash L_{1}^{R}$. It follows that $w\in (L_{2}^{R}\backslash L_{1}^{R})^{R}$, and so $L_{1}/L_{2}=(L_{2}^{R}\backslash 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