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.

$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, 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

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

Title	quotient of languages
Canonical name	QuotientOfLanguages
Date of creation	2013-03-22 18:56:06
Last modified on	2013-03-22 18:56:06
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q70
Classification	msc 68Q45
Defines	quotient
Defines	left quotient
Defines	right quotient

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