Let $L_1,L_2$ be two languages over some alphabet $\Sigma$ . The quotient of $L_1$ by $L_2$ is defined to be the set $$L_1/L_2:=\lbrace u \in \Sigma^* \mid uv \in L_1 \mbox{ for some } v\in L_2\rbrace.$$ $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 L_2:= \lbrace u\in \Sigma^* \mid vu \in L_1 \mbox{ for some } v\in L_2 \rbrace.$$ $L_1\backslash L_2$ is sometimes written $L_2^{-1} L_1$ .

Below are some examples of quotients:

• If $L_1 = \lbrace a^n b^n c^n \mid n\ge 0\rbrace$ and $L_2 = \lbrace b,c\rbrace^*$ , then
  • $L_1 / L_2 = \lbrace a^m b^n \mid m\ge n \ge 0 \rbrace$
  • $L_2 / L_1 = L_2$
  • $L_1 \backslash L_2 = \lbrace \lambda \rbrace$ , the singleton consisting the empty word
  • $L_2 \backslash L_1 = L_2$
• for any language $L$ over $\Sigma$ :
  • $L / \Sigma^*$ is the language of all prefixes of words of $L$
  • $\Sigma^* / L = \Sigma^*$
  • $L \backslash \Sigma^*$ is the language of all suffixes of words of $L$
  • $\Sigma^* \backslash L = \Sigma^*$
• $\lambda \in L/L \cap L\backslash L$ , and if $\lambda \in L$ , then $L \subseteq L/L \cap L\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 L_2)$ .
2. $(L_1/L_2)L_2 \subseteq (L_1L_2)/L_2$ , and $L_2 (L_1 \backslash L_2) \subseteq (L_2L_1) \backslash L_2$ .
3. right and left quotients are related via reversal: \begin{eqnarray*} (L_1\backslash L_2)^R &=& \lbrace u^R \mid vu \in L_1 \mbox{ for some } v\in L_2 \rbrace \\ &=& \lbrace u^R \mid (vu)^R \in L_1^R \mbox{ for some } v^R \in L_2^R \rbrace \\ &=& \lbrace u^R \mid u^Rv^R \in L_1^R \mbox{ for some } v^R \in L_2^R \rbrace \\ &=& L_1^R / L_2^R. \end{eqnarray*}

A family of languages is said to be closed under quotient by a language $L$ if for every language , . Furthermore, is said to be closed under quotient if for any . 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.

Bibliography

1

J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).