quotient of languages

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}:=\{u\in\Sigma^{*}\mid uv\in L_{1}\mbox{ 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 L_{2}:=\{u\in\Sigma^{*}\mid vu\in L_{1}\mbox{ for some }v\in L% _{2}\}.$

$L_{1}\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\geq 0\}$ and $L_{2}=\{b,c\}^{*}$, then

• $L_{1}/L_{2}=\{a^{m}b^{n}\mid m\geq n\geq 0\}$

• $L_{2}/L_{1}=L_{2}$

• $L_{1}\backslash L_{2}=\{\lambda\}$, 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. 1.

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

2. 2.

$(L_{1}/L_{2})L_{2}\subseteq(L_{1}L_{2})/L_{2}$, and $L_{2}(L_{1}\backslash L_{2})\subseteq(L_{2}L_{1})\backslash L_{2}$.

3. 3.

right and left quotients are related via reversal:

 $\displaystyle(L_{1}\backslash L_{2})^{R}$ $\displaystyle=$ $\displaystyle\{u^{R}\mid vu\in L_{1}\mbox{ for some }v\in L_{2}\}$ $\displaystyle=$ $\displaystyle\{u^{R}\mid(vu)^{R}\in L_{1}^{R}\mbox{ for some }v^{R}\in L_{2}^{% R}\}$ $\displaystyle=$ $\displaystyle\{u^{R}\mid u^{R}v^{R}\in L_{1}^{R}\mbox{ for some }v^{R}\in L_{2% }^{R}\}$ $\displaystyle=$ $\displaystyle L_{1}^{R}/L_{2}^{R}.$

A family $\mathscr{F}$ of languages is said to be closed under quotient by a language $L$ if for every language $M\in\mathscr{F}$, $M/L\in\mathscr{F}$. Furthermore, $\mathscr{F}$ is said to be closed under quotient if $M/L\in\mathscr{F}$ for any $M,L\in\mathscr{F}$. 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.

References

Title quotient of languages QuotientOfLanguages 2013-03-22 18:56:06 2013-03-22 18:56:06 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 68Q70 msc 68Q45 quotient left quotient right quotient