In
mathematics and
computer science, the right quotient (or simply quotient) of a
language with respect to language is the language consisting of
stringsw such that wx is in for some string x in .[1] Formally:
In other words, for all the strings in that have a suffix in , the suffix is removed.
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.