Right quotient

☆ Save On Wikipedia ↗

In mathematics and computer science, the right quotient (or simply quotient) of a language L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} with respect to language L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} is the language consisting of strings w {\displaystyle w} {\displaystyle w} such that w x {\displaystyle wx} {\displaystyle wx} is in L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} for some string x {\displaystyle x} {\displaystyle x} in L 2 {\displaystyle L_{2}} {\displaystyle L_{2}}, where L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} and L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} are defined on the same alphabet Σ {\displaystyle \Sigma } {\displaystyle \Sigma }. Formally:[1][2]

L 1 / L 2 = { w ∈ Σ ∗ ∣ w L 2 ∩ L 1 ≠ ∅ } = { w ∈ Σ ∗ ∣ ∃ x ∈ L 2   :   w x ∈ L 1 } {\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid wL_{2}\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ wx\in L_{1}\}} {\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid wL_{2}\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ wx\in L_{1}\}}

where Σ ∗ {\displaystyle \Sigma ^{*}} {\displaystyle \Sigma ^{*}} is the Kleene star on Σ {\displaystyle \Sigma } {\displaystyle \Sigma }, w L 2 {\displaystyle wL_{2}} {\displaystyle wL_{2}} is the language formed by concatenating w {\displaystyle w} {\displaystyle w} with each element of L 2 {\displaystyle L_{2}} {\displaystyle L_{2}}, and ∅ {\displaystyle \varnothing } {\displaystyle \varnothing } is the empty set.

In other words, for all strings in L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} that have a suffix in L 2 {\displaystyle L_{2}} {\displaystyle L_{2}}, the suffix (right part of the string) is removed.

Similarly, the left quotient of L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} with respect to L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} is the language consisting of strings w {\displaystyle w} {\displaystyle w} such that x w {\displaystyle xw} {\displaystyle xw} is in L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} for some string x {\displaystyle x} {\displaystyle x} in L 2 {\displaystyle L_{2}} {\displaystyle L_{2}}. Formally:

L 2 ∖ L 1 = { w ∈ Σ ∗ ∣ L 2 w ∩ L 1 ≠ ∅ } = { w ∈ Σ ∗ ∣ ∃ x ∈ L 2   :   x w ∈ L 1 } {\displaystyle L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid L_{2}w\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ xw\in L_{1}\}} {\displaystyle L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid L_{2}w\cap L_{1}\neq \varnothing \}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\ \colon \ xw\in L_{1}\}}

In other words, for all strings in L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} that have a prefix in L 2 {\displaystyle L_{2}} {\displaystyle L_{2}}, the prefix (left part of the string) is removed.

Note that the operands of ∖ {\displaystyle \backslash } {\displaystyle \backslash } are in reverse order, so that L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} precedes L 1 {\displaystyle L_{1}} {\displaystyle L_{1}}.

The right and left quotients of L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} with respect to L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} may also be written as L 1 L 2 − 1 {\displaystyle L_{1}L_{2}^{-1}} {\displaystyle L_{1}L_{2}^{-1}} and L 2 − 1 L 1 {\displaystyle L_{2}^{-1}L_{1}} {\displaystyle L_{2}^{-1}L_{1}} respectively.[1][3]

Example

Consider L 1 = { a n b n c n ∣ n ≥ 0 } {\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} {\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} and L 2 = { b i c j ∣ i , j ≥ 0 } . {\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.} {\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}

If an element of L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} is split into two parts, then the right part will be in L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} if and only if the split occurs somewhere after the final a {\displaystyle a} {\displaystyle a}. Assuming this is the case, if the split occurs before the first c {\displaystyle c} {\displaystyle c} then 0 ≤ i ≤ n {\displaystyle 0\leq i\leq n} {\displaystyle 0\leq i\leq n} and j = n {\displaystyle j=n} {\displaystyle j=n}, otherwise i = 0 {\displaystyle i=0} {\displaystyle i=0} and 0 ≤ j ≤ n {\displaystyle 0\leq j\leq n} {\displaystyle 0\leq j\leq n}. For instance:

a a ∣ b b c c     ( n = 2 , i = j = 2 ) {\displaystyle aa\mid bbcc\ \ (n=2,i=j=2)} {\displaystyle aa\mid bbcc\ \ (n=2,i=j=2)}

a a a b ∣ b b c c c     ( n = 3 , i = 2 , j = 3 ) {\displaystyle aaab\mid bbccc\ \ (n=3,i=2,j=3)} {\displaystyle aaab\mid bbccc\ \ (n=3,i=2,j=3)}

a a b b c c ∣ ϵ     ( n = 2 , i = j = 0 ) {\displaystyle aabbcc\mid \epsilon \ \ (n=2,i=j=0)} {\displaystyle aabbcc\mid \epsilon \ \ (n=2,i=j=0)}

where ϵ {\displaystyle \epsilon } {\displaystyle \epsilon } is the empty string.

Thus, the left part will be either a n b n − i {\displaystyle a^{n}b^{n-i}} {\displaystyle a^{n}b^{n-i}} or a n b n c n − j {\displaystyle a^{n}b^{n}c^{n-j}} {\displaystyle a^{n}b^{n}c^{n-j}} ( 0 ≤ i , j ≤ n {\displaystyle (0\leq i,j\leq n} {\displaystyle (0\leq i,j\leq n}), and L 1 / L 2 {\displaystyle L_{1}/L_{2}} {\displaystyle L_{1}/L_{2}} can be written as:

{   a p b q c r   ∣   ( p ≥ q  and  r = 0 )     or     p = q ≥ r     ;     p , q , r ≥ 0   } . {\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ (p\geq q{\text{ and }}r=0)\ \ {\text{or}}\ \ p=q\geq r\ \ ;\ \ p,q,r\geq 0\ \}.} {\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ (p\geq q{\text{ and }}r=0)\ \ {\text{or}}\ \ p=q\geq r\ \ ;\ \ p,q,r\geq 0\ \}.}

Basic properties

If L , L 1 , L 2 {\displaystyle L,L_{1},L_{2}} {\displaystyle L,L_{1},L_{2}} are languages over the same alphabet then:[3]

( L 1 ∪ L 2 ) / L   =   L 1 / L   ∪   L 2 / L {\displaystyle (L_{1}\cup L_{2})/L\ =\ L_{1}/L\ \cup \ L_{2}/L} {\displaystyle (L_{1}\cup L_{2})/L\ =\ L_{1}/L\ \cup \ L_{2}/L} ( L 1 ∪ L 2 ) ∖ L   =   L 1 ∖ L   ∪   L 2 ∖ L {\displaystyle (L_{1}\cup L_{2})\backslash L\ =\ L_{1}\backslash L\ \cup \ L_{2}\backslash L} {\displaystyle (L_{1}\cup L_{2})\backslash L\ =\ L_{1}\backslash L\ \cup \ L_{2}\backslash L}

( L 1 ∩ L 2 ) / L   ⊆   L 1 / L   ∩   L 2 / L {\displaystyle (L_{1}\cap L_{2})/L\ \subseteq \ L_{1}/L\ \cap \ L_{2}/L} {\displaystyle (L_{1}\cap L_{2})/L\ \subseteq \ L_{1}/L\ \cap \ L_{2}/L} ( L 1 ∩ L 2 ) ∖ L   ⊆   L 1 ∖ L   ∩   L 2 ∖ L {\displaystyle (L_{1}\cap L_{2})\backslash L\ \subseteq \ L_{1}\backslash L\ \cap \ L_{2}\backslash L} {\displaystyle (L_{1}\cap L_{2})\backslash L\ \subseteq \ L_{1}\backslash L\ \cap \ L_{2}\backslash L}

L ∖ ( L 1 ∪ L 2 )   =   L ∖ L 1   ∪   L ∖ L 2 {\displaystyle L\backslash (L_{1}\cup L_{2})\ =\ L\backslash L_{1}\ \cup \ L\backslash L_{2}} {\displaystyle L\backslash (L_{1}\cup L_{2})\ =\ L\backslash L_{1}\ \cup \ L\backslash L_{2}} L ∖ ( L 1 ∩ L 2 )   ⊆   L ∖ L 1   ∩   L ∖ L 2 {\displaystyle L\backslash (L_{1}\cap L_{2})\ \subseteq \ L\backslash L_{1}\ \cap \ L\backslash L_{2}} {\displaystyle L\backslash (L_{1}\cap L_{2})\ \subseteq \ L\backslash L_{1}\ \cap \ L\backslash L_{2}}

L 1 / L − L 2 / L   ⊆   ( L 1 − L 2 ) / L {\displaystyle L_{1}/L-L_{2}/L\ \subseteq \ (L_{1}-L_{2})/L} {\displaystyle L_{1}/L-L_{2}/L\ \subseteq \ (L_{1}-L_{2})/L} L ∖ L 1 − L ∖ L 2   ⊆   L ∖ ( L 1 − L 2 ) {\displaystyle L\backslash L_{1}-L\backslash L_{2}\ \subseteq \ L\backslash (L_{1}-L_{2})} {\displaystyle L\backslash L_{1}-L\backslash L_{2}\ \subseteq \ L\backslash (L_{1}-L_{2})}

Example proof

As an example, the third property is proved as follows:

If w ∈ ( L 1 ∩ L 2 ) / L {\displaystyle w\in (L_{1}\cap L_{2})/L} {\displaystyle w\in (L_{1}\cap L_{2})/L}, there exists x ∈ L {\displaystyle x\in L} {\displaystyle x\in L} such that w x ∈ L 1 ∩ L 2 {\displaystyle wx\in L_{1}\cap L_{2}} {\displaystyle wx\in L_{1}\cap L_{2}}. Since then w x ∈ L 1 {\displaystyle wx\in L_{1}} {\displaystyle wx\in L_{1}} and w x ∈ L 2 {\displaystyle wx\in L_{2}} {\displaystyle wx\in L_{2}}, it must be that w ∈ L 1 / L ∩ L 2 / L {\displaystyle w\in L_{1}/L\cap L_{2}/L} {\displaystyle w\in L_{1}/L\cap L_{2}/L}. Conversely, let w ∈ L 1 / L {\displaystyle w\in L_{1}/L} {\displaystyle w\in L_{1}/L} and w ∈ L 2 / L {\displaystyle w\in L_{2}/L} {\displaystyle w\in L_{2}/L}, then there exists x 1 , x 2 ∈ L {\displaystyle x_{1},x_{2}\in L} {\displaystyle x_{1},x_{2}\in L} such that w x 1 ∈ L 1 {\displaystyle wx_{1}\in L_{1}} {\displaystyle wx_{1}\in L_{1}} and w x 2 ∈ L 2 {\displaystyle wx_{2}\in L_{2}} {\displaystyle wx_{2}\in L_{2}} (given w {\displaystyle w} {\displaystyle w}, if L 1 ≠ L 2 {\displaystyle L_{1}\neq L_{2}} {\displaystyle L_{1}\neq L_{2}} then x 1 , x 2 {\displaystyle x_{1},x_{2}} {\displaystyle x_{1},x_{2}} may differ). Now w x 1 ∈ L 1 ∩   L 2 {\displaystyle wx_{1}\in L_{1}\cap \ L_{2}} {\displaystyle wx_{1}\in L_{1}\cap \ L_{2}} and w x 2 ∈ L 1 ∩   L 2 {\displaystyle wx_{2}\in L_{1}\cap \ L_{2}} {\displaystyle wx_{2}\in L_{1}\cap \ L_{2}} only if x 1 = x 2 {\displaystyle x_{1}=x_{2}} {\displaystyle x_{1}=x_{2}}, hence ( L 1 ∩ L 2 ) / L ⊆ L 1 / L ∩ L 2 / L {\displaystyle (L_{1}\cap L_{2})/L\subseteq L_{1}/L\cap L_{2}/L} {\displaystyle (L_{1}\cap L_{2})/L\subseteq L_{1}/L\cap L_{2}/L}.

For instance, let L 1 = { a a b , b b b } , {\displaystyle L_{1}=\{aab,bbb\},} {\displaystyle L_{1}=\{aab,bbb\},} L 2 = { a b b , b b b } , {\displaystyle L_{2}=\{abb,bbb\},} {\displaystyle L_{2}=\{abb,bbb\},} L = { a b , b b } {\displaystyle L=\{ab,bb\}} {\displaystyle L=\{ab,bb\}}.

Then L 1 ∩ L 2 = { b b b } {\displaystyle L_{1}\cap L_{2}=\{bbb\}} {\displaystyle L_{1}\cap L_{2}=\{bbb\}}, hence ( L 1 ∩ L 2 ) / L = { b } {\displaystyle (L_{1}\cap L_{2})/L=\{b\}} {\displaystyle (L_{1}\cap L_{2})/L=\{b\}}.

Also L 1 / L = { a , b } {\displaystyle L_{1}/L=\{a,b\}} {\displaystyle L_{1}/L=\{a,b\}} and L 2 / L = { a , b } {\displaystyle L_{2}/L=\{a,b\}} {\displaystyle L_{2}/L=\{a,b\}}, hence L 1 / L ∩ L 2 / L = { a , b } {\displaystyle L_{1}/L\cap L_{2}/L=\{a,b\}} {\displaystyle L_{1}/L\cap L_{2}/L=\{a,b\}}.

Relationship between right and left quotients

The right and left quotients of languages L 1 {\displaystyle L_{1}} {\displaystyle L_{1}} and L 2 {\displaystyle L_{2}} {\displaystyle L_{2}} are related through the language reversals L 1 R {\displaystyle L_{1}^{R}} {\displaystyle L_{1}^{R}} and L 2 R {\displaystyle L_{2}^{R}} {\displaystyle L_{2}^{R}} by the equalities:[3]

L 1 / L 2 = ( L 2 R ∖ L 1 R ) R {\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}} {\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}} L 2 ∖ L 1 = ( L 1 R / L 2 R ) R {\displaystyle L_{2}\backslash L_{1}=(L_{1}^{R}/L_{2}^{R})^{R}} {\displaystyle L_{2}\backslash L_{1}=(L_{1}^{R}/L_{2}^{R})^{R}}

Proof

To prove the first equality, let w ∈ L 1 / L 2 {\displaystyle w\in L_{1}/L_{2}} {\displaystyle w\in L_{1}/L_{2}}. Then there exists x ∈ L 2 {\displaystyle x\in L_{2}} {\displaystyle x\in L_{2}} such that w x ∈ L 1 {\displaystyle wx\in L_{1}} {\displaystyle wx\in L_{1}}. Therefore, there must exist y ∈ L 2 R {\displaystyle y\in L_{2}^{R}} {\displaystyle y\in L_{2}^{R}} such that y w R ∈ L 1 R {\displaystyle yw^{R}\in L_{1}^{R}} {\displaystyle yw^{R}\in L_{1}^{R}}, hence by definition w R ∈ L 2 R ∖ L 1 R {\displaystyle w^{R}\in L_{2}^{R}\backslash L_{1}^{R}} {\displaystyle w^{R}\in L_{2}^{R}\backslash L_{1}^{R}}. It follows that w ∈ ( L 2 R ∖ L 1 R ) R {\displaystyle w\in (L_{2}^{R}\backslash L_{1}^{R})^{R}} {\displaystyle w\in (L_{2}^{R}\backslash L_{1}^{R})^{R}}, and so L 1 / L 2 = ( L 2 R ∖ L 1 R ) R {\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}} {\displaystyle L_{1}/L_{2}=(L_{2}^{R}\backslash L_{1}^{R})^{R}}.

The second equality is proved in a similar manner.

Other 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

References

  1. Pin, J-É. (1986). Varieties of Formal Languages. Translated by Howie, A. New York: Plenum Press. p. 14. ISBN 0306422948.
  2. Linz, Peter & Rodger, Susan H. (2023). An Introduction to Formal Languages and Automata (Seventh ed.). Burlington, MA: Jones & Bartlett Learning. pp. 112–117. ISBN 978-1284231601. (Fifth ed. at Google Books)
  3. Simovici, Dan A. (2024). Introduction to the Theory of Formal Languages. Singapore: World Scientific. pp. 11–12. doi:10.1142/13862. ISBN 978-9811294013.