In mathematics and computer science, 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} \).[1] 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 {\displaystyle L_{1}/L_{2}} L_1 / L_2 is the prefix of a string w x {\displaystyle wx} wx in \( L_{1}\), with the remainder of the word being a string in \( L_{2} \).
Similarly, the left quotient of \( L_{1} \) with \( L_{2} \) is the language consisting of strings w such that xw is in L 2 {\displaystyle L_{2}} L_{2} for some string x in \( L_{1} \). In symbols, we write:
\( L_1 \backslash L_2 = \{w \ | \ \exists x ((x \in L_1) \land (xw \in L_2))\} \)
The left quotient can be regarded as the set of postfixes that complete words from \( L_{2} \), such that the resulting word is in \( L_{1} \).
Example
Consider
\( L_1 = \{ a^n b^n c^n \ \ |\ \ n\ge 0 \} \)
and
\( L_2 = \{ b^i c^j \ \ | \ \ i,j\ge 0 \}. \)
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
\( {\displaystyle \{a^{p}b^{q}c^{r}\ \ |\ \ p=q\geq r\ \ \lor \ \ p\geq q\land 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 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.
These closure properties hold for both left and right quotients.
See also
Brzozowski derivative
References
Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Retrieved 7 July 2014.
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
