Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language $L_1$ with respect to language $L_2$ is the language consisting of strings ''w'' such that ''wx'' is in $L_1$ for some string ''x'' in Formally:
$L_1 / L_2 = \$

In other words, we take all the strings in $L_1$ that have a suffix in $L_2$, and remove this suffix.

Similarly, the left quotient of $L_1$ with respect to $L_2$ is the language consisting of strings ''w'' such that ''xw'' is in $L_1$ for some string ''x'' in $L_2$. Formally:
$L_2 \backslash L_1 = \$

In other words, we take all the strings in $L_1$ that have a prefix in $L_2$, and remove this prefix.

Note that the operands of $\backslash$ are in reverse order: the first operand is $L_2$ and $L_1$ is second.

Example

Consider
$L_1 = \$
and
$L_2 = \.$

Now, if we insert a divider into an element of $L_1$, the part on the right is in $L_2$ 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 $a^n b^$ or $a^n b^n c^$; and $L_1 / L_2$ 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

References

{{reflist

Formal languages