Right quotient

From Wikipedia, the free encyclopedia

The right quotient (or simply quotient) of a formal language L1 with a formal language L2 is the language consisting of strings w such that wx is in L1 for some string x in L2. In symbols, we write:

L_1 / L_2 = \{w \ | \ \exists x ((x \in L_2) \land (wx \in L_1)) \}

In other words, each string in L1 / L2 is the first part of a string in L1, with the rest being a string in L2.

[edit] Examples

Consider L1 = {anbncn} and L2 = {bicj} (where n, i, and j are nonnegative integers). Now, if we insert a divider into the middle of an element of L1, the part on the right is in L2 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 anbn − i or anbncn − j; and L1 / L2 can be written as \{ a^p b^q c^r \ \ | \ \ p = q \ge r \ \ \or \ \ p \ge q \and r = 0 \}.

[edit] Properties

Some common closure properties of the right quotient 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.

[edit] Left and right quotients

There is a related notion of left quotient, which keeps the postfixes of L1 without the prefixes in L2. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.