Quotient of a formal language
In mathematics and computer science, the right quotient (or simply quotient) of a language <math>L_1</math> with respect to language <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 Template:Nowrap<ref name=Linz2011>Template:Cite book</ref> Formally: <math display="block">L_1 / L_2 = \{w \in \Sigma^* \mid \exists x \in L_2\colon\ wx \in L_1\}</math>
In other words, for all the strings in <math>L_1</math> that have a suffix in <math>L_2</math>, the suffix is removed.
Similarly, the left quotient of <math>L_1</math> with respect to <math>L_2</math> is the language consisting of strings w such that xw is in <math>L_1</math> for some string x in <math>L_2</math>. Formally: <math display="block">L_2 \backslash L_1 = \{w \in \Sigma^* \mid \exists x\in L_2\colon\ xw \in L_1\}</math>
In other words, we take all the strings in <math>L_1</math> that have a prefix in <math>L_2</math>, and remove this prefix.
Note that the operands of <math>\backslash</math> are in reverse order: the first operand is <math>L_2</math> and <math>L_1</math> is second.
ExampleEdit
Consider <math display="block">L_1 = \{ a^n b^n c^n \mid n \ge 0 \}</math> and <math display="block">L_2 = \{ b^i c^j \mid i,j \ge 0 \}.</math>
Now, if we insert a divider into an element of <math>L_1</math>, the part on the right is in <math>L_2</math> 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 <math>a^n b^{n-i}</math> or <math>a^n b^n c^{n-j}</math>; and <math>L_1 / L_2</math> can be written as <math display="block">\{\ a^p b^q c^r \ \mid\ p = q \ge r \ \ \text{or} \ \ (p \ge q \text{ and } r = 0) \ \}.</math>
PropertiesEdit
Some common closure properties of the quotient operation 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.