Right quotient
From Wikipedia, the free encyclopedia
If L1 and L2 are formal languages, then the right quotient of L1 with L2 is the language consisting of strings w such that wx is in L1 for some string x in L2. In symbols, we write:
Some common closure properties of 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 is context sensitive.
- The quotient of a context sensitive language and any other language could be anything, recursively enumerable or nonrecursively enumerable.
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.
