Right quotient
The right quotient (or simply 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
.[1] 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
.
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 (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
or
; and
can be written as

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.
Left and right quotients
There is a related notion of left quotient, which keeps the postfixes of without the prefixes in
. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.
References
- ↑ Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Retrieved 7 July 2014.