Right quotient

From Free net encyclopedia

If <math>L_1</math> and <math>L_2</math> are formal languages, then the right quotient of <math>L_1</math> with <math>L_2</math> is the language consisting of strings w such that wx is in <math>L_1</math> for some string x in <math>L_2</math>. In symbols, we write:

<math>L_1 / L_2 = \{w \ | \ \ \exists x \in L_2 \ \ : \ \ wx \in L_1\}</math>

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 <math>L_1</math> without the prefixes in <math>L_2</math>. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.