Quotient of a formal language Source: en.wikipedia.org/wiki/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 w such that wx is in ${\displaystyle L_{1}}$ for some string x in ${\displaystyle L_{2}}$, where ${\displaystyle L_{1}}$ and ${\displaystyle L_{2}}$ are defined on the same alphabet ${\displaystyle \Sigma }$.^[1] Formally:

$${\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}}$$

where ${\displaystyle \Sigma ^{*}}$is the Kleene star on ${\displaystyle \Sigma }$.

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

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

$${\displaystyle L_{2}\backslash L_{1}=\{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 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.^[2]

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:^[2]

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

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.

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 example:

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

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