Quotient of a formal language

From HandWiki

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].[1] 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

References

  1. Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. https://books.google.com/books?id=hsxDiWvVdBcC&dq=right+quotient+automata&pg=PA104. Retrieved 7 July 2014.