quotient of languages

Let $L_1,L_2$ be two languages over some alphabet $\mathrm{\Sigma }$. The quotient of $L_1$ by $L_2$ is defined to be the set

$$L_1/L_2:=\{u\in {\mathrm{\Sigma }}^{*}\mid uv\in L_1\text{ for some }v\in L_2\}.$$

$L_1/L_2$ is sometimes written $L_1{L}_2^{-1}$. The quotient so defined is also called the right quotient, for one can similarly define the left quotient of $L_1$ by $L_2$:

$$L_1\backslash \backslash L_2:=\{u\in {\mathrm{\Sigma }}^{*}\mid vu\in L_1\text{ for some }v\in L_2\}.$$

$L_1\backslash \backslash L_2$ is sometimes written $L_2^{-1}{L}_1$.

Below are some examples of quotients:

• If $L_1=\{a^n{b}^n{c}^n\mid n\ge 0\}$ and $L_2={\{b,c\}}^{*}$, then

  • $L_1/L_2=\{a^m{b}^n\mid m\ge n\ge 0\}$

  • $L_2/L_1=L_2$

  • $L_1\backslash \backslash L_2=\{\lambda \}$, the singleton consisting the empty word

  • $L_2\backslash \backslash L_1=L_2$

• for any language $L$ over $\mathrm{\Sigma }$:

  • $L/{\mathrm{\Sigma }}^{*}$ is the language of all prefixes of words of $L$

  • ${\mathrm{\Sigma }}^{*}/L={\mathrm{\Sigma }}^{*}$

  • $L\backslash \backslash {\mathrm{\Sigma }}^{*}$ is the language of all suffixes of words of $L$

  • ${\mathrm{\Sigma }}^{*}\backslash \backslash L={\mathrm{\Sigma }}^{*}$

• $\lambda \in L/L\cap L\backslash \backslash L$, and if $\lambda \in L$, then $L\subseteq L/L\cap L\backslash \backslash L$.

Here are some basic properties of quotients:

1. $L_1\subseteq (L_1/L_2)L_2\cap L_2(L_1\backslash \backslash L_2)$.

2. $(L_1/L_2)L_2\subseteq (L_1{L}_2)/L_2$, and $L_2(L_1\backslash \backslash L_2)\subseteq (L_2{L}_1)\backslash \backslash L_2$.

3. right and left quotients are related via reversal:

   ${(L_1\backslash \backslash L_2)}^R$$=$$\mathrm{\{}{u}^R\mid vu\in L_1\text{ for some }v\in L_2\}$

   $=$$\mathrm{\{}{u}^R\mid {(vu)}^R\in L_1^R\text{ for some }{v}^R\in L_2^R\}$

   $=$$\mathrm{\{}{u}^R\mid u^R{v}^R\in L_1^R\text{ for some }{v}^R\in L_2^R\}$

   $=$$L_1^R/L_2^R.$

A family $ℱ$ of languages is said to be closed under quotient by a language $L$ if for every language $M\in ℱ$, $M/L\in ℱ$. Furthermore, $ℱ$ is said to be closed under quotient if $M/L\in ℱ$ for any $M,L\in ℱ$. Closure under quotient is also termed closure under right quotient. Closure under left quotient is similarly defined.

It can be shown that the families of regular, context-free, and type-0 languages are closed under quotient (both left and right) by a regular language. The family of context-sensitive languages does not have this closure property.

Since all of the families mentioned above are closed under reversal, each of the families, except the context-sensitive family, is closed under left quotient by a regular language, according to the second property above.