Right quotient

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} is the prefix of a string wx in L_{1}, with the remainder of the word being a string in L_{2}.

Example

Consider

L_{1}=\{a^{n}b^{n}c^{n}\ \ |\ \ n\geq 0\}

and

L_{2}=\{b^{i}c^{j}\ \ |\ \ i,j\geq 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

\{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:

Left and right quotients

There is a related notion of left quotient, which keeps the postfixes of L_{1} without the prefixes in L_{2}. Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.

References

  1. ↑ Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Retrieved 7 July 2014.
This article is issued from Wikipedia - version of the Monday, July 07, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.