You are here
Homequotient of languages
Primary tabs
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}$


$\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_{1}L_{2})/L_{2}$, and $L_{2}(L_{1}\backslash L_{2})\subseteq(L_{2}L_{1})\backslash L_{2}$.
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, contextfree, and type0 languages are closed under quotient (both left and right) by a regular language. The family of contextsensitive languages does not have this closure property.
Since all of the families mentioned above are closed under reversal, each of the families, except the contextsensitive family, is closed under left quotient by a regular language, according to the second property above.
References
 1 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, AddisonWesley, (1969).
Mathematics Subject Classification
68Q70 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections