Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language ${\displaystyle L_{1}}$ with respect to language ${\displaystyle L_{2}}$ is the language consisting of strings ${\displaystyle w}$ such that ${\displaystyle wx}$ is in ${\displaystyle L_{1}}$ for some string ${\displaystyle x}$ in ${\displaystyle L_{2}}$, where ${\displaystyle L_{1}}$ and ${\displaystyle L_{2}}$ are defined on the same alphabet ${\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}\}}$$

where ${\displaystyle \Sigma ^{*}}$ is the Kleene star on ${\displaystyle \Sigma }$, ${\displaystyle wL_{2}}$ is the language formed by concatenating ${\displaystyle w}$ with each element of ${\displaystyle L_{2}}$, and ${\displaystyle \varnothing }$ is the empty set.

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

Similarly, the left quotient of ${\displaystyle L_{1}}$ with respect to ${\displaystyle L_{2}}$ is the language consisting of strings ${\displaystyle w}$ such that ${\displaystyle xw}$ is in ${\displaystyle L_{1}}$ for some string ${\displaystyle x}$ in ${\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}\}}$$

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

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

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

Example

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

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

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

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

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

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

Thus, the left part will be either ${\displaystyle a^{n}b^{n-i}}$  or ${\displaystyle a^{n}b^{n}c^{n-j}}$  ${\displaystyle (0\leq i,j\leq n}$ ), and ${\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\ \}.}$$ 

Basic properties

If ${\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})\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})\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}\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\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 ${\displaystyle w\in (L_{1}\cap L_{2})/L}$ , there exists ${\displaystyle x\in L}$  such that ${\displaystyle wx\in L_{1}\cap L_{2}}$ . Since then ${\displaystyle wx\in L_{1}}$  and ${\displaystyle wx\in L_{2}}$ , it must be that ${\displaystyle w\in L_{1}/L\cap L_{2}/L}$ . Conversely, let ${\displaystyle w\in L_{1}/L}$  and ${\displaystyle w\in L_{2}/L}$ , then there exists ${\displaystyle x_{1},x_{2}\in L}$  such that ${\displaystyle wx_{1}\in L_{1}}$  and ${\displaystyle wx_{2}\in L_{2}}$  (given ${\displaystyle w}$ , if ${\displaystyle L_{1}\neq L_{2}}$  then ${\displaystyle x_{1},x_{2}}$  may differ). Now ${\displaystyle wx_{1}\in L_{1}\cap \ L_{2}}$  and ${\displaystyle wx_{2}\in L_{1}\cap \ L_{2}}$  only if ${\displaystyle x_{1}=x_{2}}$ , hence ${\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_{2}=\{abb,bbb\},}$  ${\displaystyle L=\{ab,bb\}}$ .

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

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

Relationship between right and left quotients

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

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

Proof

To prove the first equality, let ${\displaystyle w\in L_{1}/L_{2}}$ . Then there exists ${\displaystyle x\in L_{2}}$  such that ${\displaystyle wx\in L_{1}}$ . Therefore, there must exist ${\displaystyle y\in L_{2}^{R}}$  such that ${\displaystyle yw^{R}\in L_{1}^{R}}$ , hence by definition ${\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}}$ , and so ${\displaystyle 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

References

1. Pin, J-É. (1986). Varieties of Formal Languages. Translated by Howie, A. New York: Plenum Press. p. 14. ISBN 0306422948.
2. Linz, Peter & Rodger, Susan H. (2023). An Introduction to Formal Languages and Automata (Seventh ed.). Burlington, MA: Jones & Bartlett Learning. pp. 112–117. ISBN 978-1284231601. (Fifth ed. at Google Books)
3. Simovici, Dan A. (2024). Introduction to the Theory of Formal Languages. Singapore: World Scientific. pp. 11–12. doi:10.1142/13862. ISBN 978-9811294013.