Quotient of a formal language


In mathematics and computer science, the right quotient of a formal language with a formal language is the language consisting of strings w such that wx is in for some string x in. In symbols, we write:
In other words, each string in is the prefix of a string in, with the remainder of the word being a string in.
Similarly, the left quotient of with is the language consisting of strings w such that xw is in for some string x in. In symbols, we write:
The left quotient can be regarded as the set of postfixes that complete words from, such that the resulting word is in.

Example

Consider
and
Now, if we insert a divider into the middle of an element of, the part on the right is in only if the divider is placed adjacent to a b or adjacent to a c. The part on the left, therefore, will be either or ; and can be written as
.

Properties

Some common closure properties of the right quotient include:
These closure properties hold for both left and right quotients.