quotient of languages
is sometimes written . The quotient so defined is also called the right quotient, for one can similarly define the left quotient of by :
is sometimes written .
Below are some examples of quotients:
for any language over :
is the language of all prefixes of words of
is the language of all suffixes of words of
, and if , then .
Here are some basic properties of quotients:
, and .
right and left quotients are related via reversal:
A family of languages is said to be closed under quotient by a language 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.
|Title||quotient of languages|
|Date of creation||2013-03-22 18:56:06|
|Last modified on||2013-03-22 18:56:06|
|Last modified by||CWoo (3771)|