Quotient of a formal language

In mathematics and computer science, the right quotient (or simply quotient) of a language L_1 with respect to language L_2 is the language consisting of strings w such that wx is in L_1 for some string x in {{nowrap|L_2,}} where L_1 and L_2 are defined on the same alphabet {{nowrap|\Sigma.}} Formally:{{cite book |last=Pin |first=J-É. |author-link=Jean-Éric Pin |translator-last=Howie |translator-first=A. |date=1986 |title=Varieties of Formal Languages |location=New York |publisher=Plenum Press |isbn=0306422948 |pages=14}}{{cite book |last1=Linz |first1=Peter |last2=Rodger |first2=Susan H. |author-link2=Susan H. Rodger |name-list-style=amp |date=2023 |title=An Introduction to Formal Languages and Automata |edition=Seventh |location=Burlington, MA |publisher=Jones & Bartlett Learning |isbn=978-1284231601 |pages=112–117}} ([https://books.google.com/books?id=hsxDiWvVdBcC&dq=right+quotient+automata&pg=PA104 Fifth ed.] at Google Books)

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 \Sigma^* is the Kleene star on \Sigma, wL_2 is the language formed by concatenating w with each element of {{nowrap|L_2,}} and \varnothing is the empty set.

In other words, for all strings in L_1 that have a suffix in L_2, the suffix (right part of the string) is removed.

Similarly, the left quotient of L_1 with respect to L_2 is the language consisting of strings w such that xw is in L_1 for some string x in L_2. Formally:

L_2 \backslash L_1 = \{w \in \Sigma^* \mid L_2w \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 that have a prefix in L_2, the prefix (left part of the string) is removed.

Note that the operands of \backslash are in reverse order, so that L_2 preceeds L_1.

The right and left quotients of L_1 with respect to L_2 may also be written as L_1 L_2^{-1} and L_2^{-1} L_1 respectively.{{cite book |last=Simovici |first=Dan A. |date=2024 |title=Introduction to the Theory of Formal Languages |location=Singapore |publisher=World Scientific |isbn=978-9811294013 |doi=10.1142/13862 |pages=11–12}}

Example

Consider

L_1 = \{ a^n b^n c^n \mid n \ge 0 \}

and

L_2 = \{ b^i c^j \mid i,j \ge 0 \}.

If an element of L_1 is split into two parts, then the right part will be in L_2 if and only if the split occurs somewhere after the final {{nowrap|a.}} Assuming this is the case, if the split occurs before the first c then 0 \le i \le n and {{nowrap|j=n}}, otherwise i=0 and {{nowrap|0 \le j \le n.}} For instance:

aa \mid bbcc \ \ (n=2, i=j=2)

aaab \mid bbccc \ \ (n=3, i=2, j=3)

aabbcc \mid \epsilon \ \ (n=2, i=j=0)

where \epsilon is the empty string.

Thus, the left part will be either a^n b^{n-i} or {{nowrap|a^n b^n c^{n-j}}} {{nowrap|(0 \le i,j \le n),}} and L_1 / L_2 can be written as:

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

Basic properties

If L, L_1, L_2 are languages over the same alphabet then:

(L_1 \cup L_2) / L \ = \ L_1 / L \ \cup \ L_2 / L

(L_1 \cup L_2) \backslash L \ = \ L_1 \backslash L \ \cup \ L_2 \backslash L

(L_1 \cap L_2) / L \ \subseteq \ L_1 / L \ \cap \ L_2 / L

(L_1 \cap L_2) \backslash L \ \subseteq \ L_1 \backslash L \ \cap \ L_2 \backslash L

L \backslash (L_1 \cup L_2) \ = \ L \backslash L_1 \ \cup \ L \backslash L_2

L \backslash (L_1 \cap L_2) \ \subseteq \ L \backslash L_1 \ \cap \ L \backslash L_2

L_1 / L - L_2 / L \ \subseteq \ (L_1 - L_2) / L

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 {{nowrap|w \in (L_1 \cap L_2) / L,}} there exists x \in L such that {{no wrap|wx \in L_1 \cap L_2.}} Since then wx \in L_1 and {{nowrap|wx \in L_2,}} it must be that {{nowrap|w \in L_1 / L \cap L_2 / L.}} Conversely, let w \in L_1 / L and {{nowrap|w \in L_2 / L,}} then there exists x_1, x_2 \in L such that wx_1 \in L_1 and wx_2 \in L_2 (given {{nowrap|w,}} if L_1 \neq L_2 then x_1,x_2 may differ). Now wx_1 \in L_1 \cap \ L_2 and wx_2 \in L_1 \cap \ L_2 only if {{nowrap|x_1 = x_2,}} hence {{nowrap|(L_1 \cap L_2) / L \subseteq L_1 / L \cap L_2 / L.}}

For instance, let L_1 = \{aab, bbb\}, L_2 = \{abb, bbb\}, {{nowrap|L = \{ab, bb\}.}}

Then {{no wrap|L_1 \cap L_2 = \{bbb\}}}, hence {{nowrap|(L_1 \cap L_2) / L = \{b\}.}}

Also L_1 / L = \{a, b\} and {{nowrap|L_2 / L = \{a, b\}}}, hence {{nowrap|L_1 / L \cap L_2 / L = \{a, b\}.}}

Relationship between right and left quotients

The right and left quotients of languages L_1 and L_2 are related through the language reversals L_1^R and L_2^R by the equalities:

L_1 / L_2 = (L_2^R \backslash L_1^R)^R

L_2 \backslash L_1 = (L_1^R / L_2^R)^R

=Proof=

To prove the first equality, let {{nowrap|w \in L_1 / L_2.}} Then there exists x \in L_2 such that {{nowrap|wx \in L_1.}} Therefore, there must exist y \in L_2^R such that {{nowrap|yw^R \in L_1^R,}} hence by definition {{nowrap|w^R \in L_2^R \backslash L_1^R.}} It follows that {{nowrap|w \in (L_2^R \backslash L_1^R)^R,}} and so {{nowrap|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