Login
Login

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 {{nowrap|L_2.}}{{cite book|last1=Linz| first1=Peter|title=An Introduction to Formal Languages and Automata|date=2011| publisher=Jones & Bartlett Publishers| isbn=9781449615529|pages=104–108| url=https://books.google.com/books?id=hsxDiWvVdBcC&dq=right+quotient+automata&pg=PA104| access-date=7 July 2014}} Formally:

L_1 / L_2 = \{w \in \Sigma^* \mid \exists x \in L_2\colon\ wx \in L_1\}

In other words, for all the strings in L_1 that have a suffix in L_2, the suffix is removed.

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 = \{w \in \Sigma^* \mid \exists x\in L_2\colon\ xw \in 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 = \{ a^n b^n c^n \mid n \ge 0 \}

and

L_2 = \{ b^i c^j \mid i,j \ge 0 \}.

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^{n-i} or a^n b^n c^{n-j}; and L_1 / L_2 can be written as

\{\ a^p b^q c^r \ \mid\ p = q \ge r \ \ \text{or} \ \ (p \ge q \text{ and } r = 0) \ \}.

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

{{reflist}}

Category:Formal languages