Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language [math]\displaystyle{ L_1 }[/math] with respect to language [math]\displaystyle{ L_2 }[/math] is the language consisting of strings w such that wx is in [math]\displaystyle{ L_1 }[/math] for some string x in [math]\displaystyle{ L_2 }[/math]. Formally: [math]\displaystyle{ L_1 / L_2 = \{w \in \Sigma^* \mid \exists x \in L_2\colon\ wx \in L_1\} }[/math]

In other words, we take all the strings in [math]\displaystyle{ L_1 }[/math] that have a suffix in [math]\displaystyle{ L_2 }[/math], and remove this suffix.

Similarly, the left quotient of [math]\displaystyle{ L_1 }[/math] with respect to [math]\displaystyle{ L_2 }[/math] is the language consisting of strings w such that xw is in [math]\displaystyle{ L_1 }[/math] for some string x in [math]\displaystyle{ L_2 }[/math]. Formally: [math]\displaystyle{ L_2 \backslash L_1 = \{w \in \Sigma^* \mid \exists x\in L_2\colon\ xw \in L_1\} }[/math]

In other words, we take all the strings in [math]\displaystyle{ L_1 }[/math] that have a prefix in [math]\displaystyle{ L_2 }[/math], and remove this prefix.

Note that the operands of [math]\displaystyle{ \backslash }[/math] are in reverse order: the first operand is [math]\displaystyle{ L_2 }[/math] and [math]\displaystyle{ L_1 }[/math] is second.

Example

Consider [math]\displaystyle{ L_1 = \{ a^n b^n c^n \mid n \ge 0 \} }[/math] and [math]\displaystyle{ L_2 = \{ b^i c^j \mid i,j \ge 0 \}. }[/math]

Now, if we insert a divider into an element of [math]\displaystyle{ L_1 }[/math], the part on the right is in [math]\displaystyle{ L_2 }[/math] 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 [math]\displaystyle{ a^n b^{n-i} }[/math] or [math]\displaystyle{ a^n b^n c^{n-j} }[/math]; and [math]\displaystyle{ L_1 / L_2 }[/math] can be written as [math]\displaystyle{ \{\ a^p b^q c^r \ \mid\ p = q \ge r \ \ \text{or} \ \ (p \ge q \text{ and } r = 0) \ \}. }[/math]

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