- Right quotient
The right quotient (or simply quotient) of a
formal language L_1 with a formal language L_2 is the language consisting of strings "w" such that "wx" is in L_1 for some string "x" in L_2. 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 L_1 / L_2 is the first part of a string in L_1, with the rest being a string in L_2.
Examples
Consider L_1 = { a^n b^n c^n } and L_2 = { b^i c^j } (where "n", "i", and "j" are nonnegative integers). Now, if we insert a divider into the middle of 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 | p = q ge r or p ge q and r = 0 }.
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 acontext free language with a regular language is context free.
* The quotient of two context free languages can be anyrecursively enumerable language.
* The quotient of two recursively enumerable languages is recursively enumerable.Left and right quotients
There is a related notion of
left quotient , which keeps the postfixes of L_1 without the prefixes in L_2. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.
Wikimedia Foundation. 2010.