In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the right quotient (or simply quotient) of a
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
with respect to language
is the language consisting of
strings ''w'' such that ''wx'' is in
for some string ''x'' in
Formally:
In other words, we take all the strings in
that have a suffix in
, and remove this suffix.
Similarly, the left quotient of
with respect to
is the language consisting of strings ''w'' such that ''xw'' is in
for some string ''x'' in
. Formally:
In other words, we take all the strings in
that have a prefix in
, and remove this prefix.
Note that the operands of
are in reverse order: the first operand is
and
is second.
Example
Consider
and
Now, if we insert a divider into an element of
, the part on the right is in
only if the divider is placed adjacent to a ''b'' (in which case ''i'' ≤ ''n'' and ''j'' = ''n'') or adjacent to a ''c'' (in which case ''i'' = 0 and ''j'' ≤ ''n''). The part on the left, therefore, will be either
or
; and
can be written as
Properties
Some common closure properties of the quotient operation include:
* The quotient of a
regular language with any other language is regular.
* The quotient of a
context free language with a regular language is context free.
* The quotient of two context free languages can be any
recursively enumerable language.
* The quotient of two recursively enumerable languages is recursively enumerable.
These closure properties hold for both left and right quotients.
See also
*
Brzozowski derivative
In theoretical computer science, in particular in formal language theory, the Brzozowski derivative u^S of a set S of strings and a string u is the set of all strings obtainable from a string in S by cutting off the prefix u, as illustrated in ...
References
{{reflist
Formal languages