Editing Quotient of a formal language

In [[mathematics]] and [[computer science]], the '''right quotient''' (or simply '''quotient''') of a [[formal language|language]] <math>L_1</math> with respect to language <math>L_2</math> is the language consisting of [[string (computer science)|strings]] ''w'' such that ''wx'' is in <math>L_1</math> for some string ''x'' in {{nowrap|<math>L_2</math>.}}<ref name=Linz2011>{{cite book|last1=Linz| first1=Peter|title=An Introduction to Formal Languages and Automata|date=2011| publisher=Jones & Bartlett Publishers| isbn=9781449615529|pages=104–108| url=https://books.google.com/books?id=hsxDiWvVdBcC&dq=right+quotient+automata&pg=PA104| access-date=7 July 2014}}</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.

==Example==

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''&nbsp;≤&nbsp;''n'' and ''j''&nbsp;=&nbsp;''n'') or adjacent to a ''c'' (in which case ''i''&nbsp;=&nbsp;0 and ''j''&nbsp;≤&nbsp;''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>

==Properties==
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.

== See also ==

* [[Brzozowski derivative]]

==References==
{{reflist}}

[[Category:Formal languages]]