Quotient of a formal language


In mathematics and computer science, the right quotient of a language with respect to language is the language consisting of strings such that is in for some string in where and are defined on the same alphabet Formally:
where is the Kleene star on, is the language formed by concatenating with each element of and is the empty set.
In other words, for all 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 such that is in for some string in. Formally:
In other words, for all strings in that have a prefix in, the prefix is removed.
Note that the operands of are in reverse order, so that precedes.
The right and left quotients of with respect to may also be written as and respectively.

Example

Consider
and
If an element of is split into two parts, then the right part will be in if and only if the split occurs somewhere after the final Assuming this is the case, if the split occurs before the first then and, otherwise and For instance:
where is the empty string.
Thus, the left part will be either or and can be written as:

Basic properties

If are languages over the same alphabet then:

Example proof

As an example, the third property is proved as follows:
If there exists such that Since then and it must be that Conversely, let and then there exists such that and . Now and only if hence
For instance, let
Then, hence
Also and, hence

Relationship between right and left quotients

The right and left quotients of languages and are related through the language reversals and by the equalities:

Proof

To prove the first equality, let Then there exists such that Therefore, there must exist such that hence by definition It follows that and so
The second equality is proved in a similar manner.

Other properties

Some common closure properties of the quotient operation include:
These closure properties hold for both left and right quotients.