Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language ${\displaystyle L_{1}}${\displaystyle L_{1}} with respect to language ${\displaystyle L_{2}}${\displaystyle L_{2}} is the language consisting of strings ${\displaystyle w}${\displaystyle w} such that ${\displaystyle wx}${\displaystyle wx} is in ${\displaystyle L_{1}}${\displaystyle L_{1}} for some string ${\displaystyle x}${\displaystyle x} in ${\displaystyle L_{2}}${\displaystyle L_{2}}, where ${\displaystyle L_{1}}${\displaystyle L_{1}} and ${\displaystyle L_{2}}${\displaystyle L_{2}} are defined on the same alphabet ${\displaystyle \Sigma }${\displaystyle \Sigma }. Formally:^{[1] [2]}

$${\displaystyle 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}\}}$${\displaystyle 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 ${\displaystyle \Sigma ^{*}}${\displaystyle \Sigma ^{*}} is the Kleene star on ${\displaystyle \Sigma }${\displaystyle \Sigma }, ${\displaystyle wL_{2}}${\displaystyle wL_{2}} is the language formed by concatenating ${\displaystyle w}${\displaystyle w} with each element of ${\displaystyle L_{2}}${\displaystyle L_{2}}, and ${\displaystyle \varnothing }${\displaystyle \varnothing } is the empty set.

In other words, for all strings in ${\displaystyle L_{1}}${\displaystyle L_{1}} that have a suffix in ${\displaystyle L_{2}}${\displaystyle L_{2}}, the suffix (right part of the string) is removed.

Similarly, the left quotient of ${\displaystyle L_{1}}${\displaystyle L_{1}} with respect to ${\displaystyle L_{2}}${\displaystyle L_{2}} is the language consisting of strings ${\displaystyle w}${\displaystyle w} such that ${\displaystyle xw}${\displaystyle xw} is in ${\displaystyle L_{1}}${\displaystyle L_{1}} for some string ${\displaystyle x}${\displaystyle x} in ${\displaystyle L_{2}}${\displaystyle L_{2}}. Formally:

$${\displaystyle 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}\}}$${\displaystyle 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 ${\displaystyle L_{1}}${\displaystyle L_{1}} that have a prefix in ${\displaystyle L_{2}}${\displaystyle L_{2}}, the prefix (left part of the string) is removed.

Note that the operands of ${\displaystyle \backslash }${\displaystyle \backslash } are in reverse order, so that ${\displaystyle L_{2}}${\displaystyle L_{2}} preceeds ${\displaystyle L_{1}}${\displaystyle L_{1}}.

The right and left quotients of ${\displaystyle L_{1}}${\displaystyle L_{1}} with respect to ${\displaystyle L_{2}}${\displaystyle L_{2}} may also be written as ${\displaystyle L_{1}L_{2}^{-1}}${\displaystyle L_{1}L_{2}^{-1}} and ${\displaystyle L_{2}^{-1}L_{1}}${\displaystyle L_{2}^{-1}L_{1}} respectively.^{[1] [3]}

Consider $${\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$${\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} and $${\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}$${\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}

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

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

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

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

where ${\displaystyle \epsilon }${\displaystyle \epsilon } is the empty string.

Thus, the left part will be either ${\displaystyle a^{n}b^{n-i}}${\displaystyle a^{n}b^{n-i}} or ${\displaystyle a^{n}b^{n}c^{n-j}}${\displaystyle a^{n}b^{n}c^{n-j}} ${\displaystyle (0\leq i,j\leq n}${\displaystyle (0\leq i,j\leq n}), and ${\displaystyle L_{1}/L_{2}}${\displaystyle L_{1}/L_{2}} can be written as:

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

If ${\displaystyle L,L_{1},L_{2}}${\displaystyle L,L_{1},L_{2}} are languages over the same alphabet then:^[3]

$${\displaystyle (L_{1}\cup L_{2})/L\ =\ L_{1}/L\ \cup \ L_{2}/L}$${\displaystyle (L_{1}\cup L_{2})/L\ =\ L_{1}/L\ \cup \ L_{2}/L} $${\displaystyle (L_{1}\cup L_{2})\backslash L\ =\ L_{1}\backslash L\ \cup \ L_{2}\backslash L}$${\displaystyle (L_{1}\cup L_{2})\backslash L\ =\ L_{1}\backslash L\ \cup \ L_{2}\backslash L}

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

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

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

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

If ${\displaystyle w\in (L_{1}\cap L_{2})/L}${\displaystyle w\in (L_{1}\cap L_{2})/L}, there exists ${\displaystyle x\in L}${\displaystyle x\in L} such that ${\displaystyle wx\in L_{1}\cap L_{2}}${\displaystyle wx\in L_{1}\cap L_{2}}. Since then ${\displaystyle wx\in L_{1}}${\displaystyle wx\in L_{1}} and ${\displaystyle wx\in L_{2}}${\displaystyle wx\in L_{2}}, it must be that ${\displaystyle w\in L_{1}/L\cap L_{2}/L}${\displaystyle w\in L_{1}/L\cap L_{2}/L}. Conversely, let ${\displaystyle w\in L_{1}/L}${\displaystyle w\in L_{1}/L} and ${\displaystyle w\in L_{2}/L}${\displaystyle w\in L_{2}/L}, then there exists ${\displaystyle x_{1},x_{2}\in L}${\displaystyle x_{1},x_{2}\in L} such that ${\displaystyle wx_{1}\in L_{1}}${\displaystyle wx_{1}\in L_{1}} and ${\displaystyle wx_{2}\in L_{2}}${\displaystyle wx_{2}\in L_{2}} (given ${\displaystyle w}${\displaystyle w}, if ${\displaystyle L_{1}\neq L_{2}}${\displaystyle L_{1}\neq L_{2}} then ${\displaystyle x_{1},x_{2}}${\displaystyle x_{1},x_{2}} may differ). Now ${\displaystyle wx_{1}\in L_{1}\cap \ L_{2}}${\displaystyle wx_{1}\in L_{1}\cap \ L_{2}} and ${\displaystyle wx_{2}\in L_{1}\cap \ L_{2}}${\displaystyle wx_{2}\in L_{1}\cap \ L_{2}} only if ${\displaystyle x_{1}=x_{2}}${\displaystyle x_{1}=x_{2}}, hence ${\displaystyle (L_{1}\cap L_{2})/L\subseteq L_{1}/L\cap L_{2}/L}${\displaystyle (L_{1}\cap L_{2})/L\subseteq L_{1}/L\cap L_{2}/L}.

For instance, let ${\displaystyle L_{1}=\{aab,bbb\},}${\displaystyle L_{1}=\{aab,bbb\},} ${\displaystyle L_{2}=\{abb,bbb\},}${\displaystyle L_{2}=\{abb,bbb\},} ${\displaystyle L=\{ab,bb\}}${\displaystyle L=\{ab,bb\}}.

Then ${\displaystyle L_{1}\cap L_{2}=\{bbb\}}${\displaystyle L_{1}\cap L_{2}=\{bbb\}}, hence ${\displaystyle (L_{1}\cap L_{2})/L=\{b\}}${\displaystyle (L_{1}\cap L_{2})/L=\{b\}}.

Also ${\displaystyle L_{1}/L=\{a,b\}}${\displaystyle L_{1}/L=\{a,b\}} and ${\displaystyle L_{2}/L=\{a,b\}}${\displaystyle L_{2}/L=\{a,b\}}, hence ${\displaystyle L_{1}/L\cap L_{2}/L=\{a,b\}}${\displaystyle L_{1}/L\cap L_{2}/L=\{a,b\}}.

The right and left quotients of languages ${\displaystyle L_{1}}${\displaystyle L_{1}} and ${\displaystyle L_{2}}${\displaystyle L_{2}} are related through the language reversals ${\displaystyle L_{1}^{R}}${\displaystyle L_{1}^{R}} and ${\displaystyle L_{2}^{R}}${\displaystyle L_{2}^{R}} by the equalities:^[3]

$${\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}}$${\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}} $${\displaystyle L_{2}\backslash L_{1}=(L_{1}^{R}/L_{2}^{R})^{R}}$${\displaystyle L_{2}\backslash L_{1}=(L_{1}^{R}/L_{2}^{R})^{R}}

To prove the first equality, let ${\displaystyle w\in L_{1}/L_{2}}${\displaystyle w\in L_{1}/L_{2}}. Then there exists ${\displaystyle x\in L_{2}}${\displaystyle x\in L_{2}} such that ${\displaystyle wx\in L_{1}}${\displaystyle wx\in L_{1}}. Therefore, there must exist ${\displaystyle y\in L_{2}^{R}}${\displaystyle y\in L_{2}^{R}} such that ${\displaystyle yw^{R}\in L_{1}^{R}}${\displaystyle yw^{R}\in L_{1}^{R}}, hence by definition ${\displaystyle w^{R}\in L_{2}^{R}\backslash L_{1}^{R}}${\displaystyle w^{R}\in L_{2}^{R}\backslash L_{1}^{R}}. It follows that ${\displaystyle w\in (L_{2}^{R}\backslash L_{1}^{R})^{R}}${\displaystyle w\in (L_{2}^{R}\backslash L_{1}^{R})^{R}}, and so ${\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}}${\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}}.

The second equality is proved in a similar manner.

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.

• Brzozowski derivative

• Formal languages