Quotient of a formal language: Difference between revisions

Latest revision as of 09:03, 1 July 2025

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 $w x$ is in $L_{1}$ for some string $x$ in $L_{2}$ , where $L_{1}$ and $L_{2}$ are defined on the same alphabet $Σ$ . Formally:^[1]^[2]

$L_{1} / L_{2} = {w \in Σ^{*} ∣ w L_{2} \cap L_{1} \neq \emptyset} = {w \in Σ^{*} ∣ \exists x \in L_{2} : w x \in L_{1}}$

where $Σ^{*}$ is the Kleene star on $Σ$ , $w L_{2}$ is the language formed by concatenating $w$ with each element of $L_{2}$ , and $\emptyset$ 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 $x w$ is in $L_{1}$ for some string $x$ in $L_{2}$ . Formally:

$L_{2} ∖ L_{1} = {w \in Σ^{*} ∣ L_{2} w \cap L_{1} \neq \emptyset} = {w \in Σ^{*} ∣ \exists x \in L_{2} : x w \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 $∖$ 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.^[1]^[3]

Example

Consider $L_{1} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ and $L_{2} = {b^{i} c^{j} ∣ i, j \geq 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 $a$ . Assuming this is the case, if the split occurs before the first $c$ then $0 \leq i \leq n$ and $j = n$ , otherwise $i = 0$ and $0 \leq j \leq n$ . For instance:

$a a ∣ b b c c (n = 2, i = j = 2)$

$a a a b ∣ b b c c c (n = 3, i = 2, j = 3)$

$a a b b c c ∣ ϵ (n = 2, i = j = 0)$

where $ϵ$ is the empty string.

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

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

Basic properties

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

$(L_{1} \cup L_{2}) / L = L_{1} / L \cup L_{2} / L$ $(L_{1} \cup L_{2}) ∖ L = L_{1} ∖ L \cup L_{2} ∖ L$

$(L_{1} \cap L_{2}) / L \subseteq L_{1} / L \cap L_{2} / L$ $(L_{1} \cap L_{2}) ∖ L \subseteq L_{1} ∖ L \cap L_{2} ∖ L$

$L ∖ (L_{1} \cup L_{2}) = L ∖ L_{1} \cup L ∖ L_{2}$ $L ∖ (L_{1} \cap L_{2}) \subseteq L ∖ L_{1} \cap L ∖ L_{2}$

$L_{1} / L - L_{2} / L \subseteq (L_{1} - L_{2}) / L$ $L ∖ L_{1} - L ∖ L_{2} \subseteq L ∖ (L_{1} - L_{2})$

Example proof

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

If $w \in (L_{1} \cap L_{2}) / L$ , there exists $x \in L$ such that Template:No wrap Since then $w x \in L_{1}$ and $w x \in L_{2}$ , it must be that $w \in L_{1} / L \cap L_{2} / L$ . Conversely, let $w \in L_{1} / L$ and $w \in L_{2} / L$ , then there exists $x_{1}, x_{2} \in L$ such that $w x_{1} \in L_{1}$ and $w x_{2} \in L_{2}$ (given $w$ , if $L_{1} \neq L_{2}$ then $x_{1}, x_{2}$ may differ). Now $w x_{1} \in L_{1} \cap L_{2}$ and $w x_{2} \in L_{1} \cap L_{2}$ only if $x_{1} = x_{2}$ , hence $(L_{1} \cap L_{2}) / L \subseteq L_{1} / L \cap L_{2} / L$ .

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:^[3]

$L_{1} / L_{2} = (L_{2}^{R} ∖ L_{1}^{R})^{R}$ $L_{2} ∖ L_{1} = (L_{1}^{R} / L_{2}^{R})^{R}$

Proof

To prove the first equality, let $w \in L_{1} / L_{2}$ . Then there exists $x \in L_{2}$ such that $w x \in L_{1}$ . Therefore, there must exist $y \in L_{2}^{R}$ such that $y w^{R} \in L_{1}^{R}$ , hence by definition $w^{R} \in L_{2}^{R} ∖ L_{1}^{R}$ . It follows that $w \in (L_{2}^{R} ∖ L_{1}^{R})^{R}$ , and so $L_{1} / L_{2} = (L_{2}^{R} ∖ 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.

References

Template:Reflist

↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1". (Fifth ed. at Google Books)
↑ ^a ^b ^c Script error: No such module "citation/CS1".

[Pin-1] Script error: No such module "citation/CS1".

[Linz-2] Script error: No such module "citation/CS1". (Fifth ed. at Google Books)

[Simovici-3] Script error: No such module "citation/CS1".

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-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:
+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]] <math>w</math> such that <math>wx</math> is in <math>L_1</math> for some string <math>x</math> in {{nowrap|<math>L_2</math>,}} where <math>L_1</math> and <math>L_2</math> are defined on the same [[alphabet (formal languages)|alphabet]] {{nowrap|<math>\Sigma</math>.}} Formally:<ref name="Pin">{{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}}</ref><ref name="Linz">{{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]])</ref>
-<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.
+<math display="block">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\}</math>
-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:
+where <math>\Sigma^*</math> is the [[Kleene star]] on <math>\Sigma</math>, <math>wL_2</math> is the language formed by [[Concatenation|concatenating]] <math>w</math> with each element of {{nowrap|<math>L_2</math>,}} and <math>\varnothing</math> is the [[empty set]].
-<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.
+In other words, for all strings in <math>L_1</math> that have a [[Substring#Suffix|suffix]] in <math>L_2</math>, the suffix (right part of the string) is removed.
-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.
+Similarly, the '''left quotient''' of <math>L_1</math> with respect to <math>L_2</math> is the language consisting of strings <math>w</math> such that <math>xw</math> is in <math>L_1</math> for some string <math>x</math> in <math>L_2</math>. Formally:
+<math display="block">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\}</math>
+In other words, for all strings in <math>L_1</math> that have a [[Substring#Prefix|prefix]] in <math>L_2</math>, the prefix (left part of the string) is removed.
+Note that the [[operand]]s of <math>\backslash</math> are in reverse order, so that <math>L_2</math> preceeds <math>L_1</math>.
+The right and left quotients of <math>L_1</math> with respect to <math>L_2</math> may also be written as <math>L_1 L_2^{-1}</math> and <math>L_2^{-1} L_1</math> respectively.<ref name="Pin"/><ref name="Simovici">{{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}}</ref>
 ==Example==
@@ Line 18: / Line 24: @@
 <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
+If an element of <math>L_1</math> is split into two parts, then the right part will be in <math>L_2</math> if and only if the split occurs somewhere after the final {{nowrap|<math>a</math>.}} Assuming this is the case, if the split occurs before the first <math>c</math> then <math>0 \le i \le n</math> and {{nowrap|<math>j=n</math>}}, otherwise  <math>i=0</math> and {{nowrap|<math>0 \le j \le n</math>.}} For instance:
-<math display="block">\{\ a^p b^q c^r \ \mid\  p = q \ge r \ \ \text{or} \ \ (p \ge q \text{ and } r = 0) \ \}.</math>
+<math>aa \mid bbcc \ \ (n=2, i=j=2)</math>
+<math>aaab \mid bbccc \ \ (n=3, i=2, j=3)</math>
+<math>aabbcc \mid \epsilon \ \ (n=2, i=j=0)</math>
+where <math>\epsilon</math> is the [[empty string]].
+Thus, the left part will be either <math>a^n b^{n-i}</math> or {{nowrap|<math>a^n b^n c^{n-j}</math>}} {{nowrap|<math>(0 \le i,j \le n</math>),}} and <math>L_1 / L_2</math> can be written as:
+<math display="block">\{\ 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 \ \}.</math>
+==Basic properties==
+If <math>L, L_1, L_2</math> are languages over the same alphabet then:<ref name="Simovici"/>
+<math display="block">(L_1 \cup L_2) / L \ = \ L_1 / L \ \cup \ L_2 / L</math>
+<math display="block">(L_1 \cup L_2) \backslash L \ = \ L_1 \backslash L \ \cup \ L_2 \backslash L</math>
+<math display="block">(L_1 \cap L_2) / L \ \subseteq \ L_1 / L \ \cap \ L_2 / L</math>
+<math display="block">(L_1 \cap L_2) \backslash L \ \subseteq \ L_1 \backslash L \ \cap \ L_2 \backslash L</math>
+<math display="block">L \backslash (L_1 \cup L_2) \ = \ L \backslash L_1 \ \cup \ L \backslash L_2</math>
+<math display="block">L \backslash (L_1 \cap L_2) \ \subseteq \ L \backslash L_1 \ \cap \ L \backslash L_2</math>
+<math display="block">L_1 / L - L_2 / L \ \subseteq \ (L_1 - L_2) / L</math>
+<math display="block">L \backslash L_1 - L \backslash L_2 \ \subseteq \ L \backslash (L_1 - L_2) </math>
+===Example proof===
+As an example, the third property is proved as follows:
+If {{nowrap|<math>w \in (L_1 \cap L_2) / L</math>,}} there exists <math>x \in L</math> such that {{no wrap|<math>wx \in L_1 \cap L_2</math>.}} Since then <math>wx \in L_1</math> and {{nowrap|<math>wx \in L_2</math>,}} it must be that {{nowrap|<math>w \in L_1 / L \cap L_2 / L</math>.}} Conversely, let <math>w \in L_1 / L</math> and {{nowrap|<math>w \in L_2 / L</math>,}} then there exists <math>x_1, x_2 \in L</math> such that <math>wx_1 \in L_1</math> and <math>wx_2 \in L_2</math> (given {{nowrap|<math>w</math>,}} if <math>L_1 \neq L_2</math> then <math>x_1,x_2</math> may differ). Now <math>wx_1 \in L_1 \cap \ L_2</math> and <math>wx_2 \in L_1 \cap \ L_2</math> only if {{nowrap|<math>x_1 = x_2</math>,}} hence {{nowrap|<math>(L_1 \cap L_2) / L \subseteq L_1 / L \cap L_2 / L</math>.}}
+==Relationship between right and left quotients==
+The right and left quotients of languages <math>L_1</math> and <math>L_2</math> are related through the language [[Formal language#Operations on languages|reversals]] <math>L_1^R</math> and <math>L_2^R</math> by the equalities:<ref name="Simovici"/>
+<math display="block">L_1 / L_2 = (L_2^R \backslash L_1^R)^R</math>
+<math display="block">L_2 \backslash L_1 = (L_1^R / L_2^R)^R</math>
+===Proof===
+To prove the first equality, let {{nowrap|<math>w \in L_1 / L_2</math>.}} Then there exists <math>x \in L_2</math> such that {{nowrap|<math>wx \in L_1</math>.}} Therefore, there must exist <math>y \in L_2^R</math> such that {{nowrap|<math>yw^R \in L_1^R</math>,}} hence by definition {{nowrap|<math>w^R \in L_2^R \backslash L_1^R</math>.}} It follows that {{nowrap|<math>w \in (L_2^R \backslash L_1^R)^R</math>,}} and so {{nowrap|<math>L_1 / L_2 = (L_2^R \backslash L_1^R)^R</math>.}}
+The second equality is proved in a similar manner.
+==Other properties==
-==Properties==
 Some common closure properties of the quotient operation include:

Quotient of a formal language: Difference between revisions

Latest revision as of 09:03, 1 July 2025

Contents

Example

Basic properties

Example proof

Relationship between right and left quotients

Proof

Other properties

See also

References

Navigation menu

Quotient of a formal language: Difference between revisions

Latest revision as of 09:03, 1 July 2025

Example

Basic properties

Example proof

Relationship between right and left quotients

Proof

Other properties

See also

References

Navigation menu

Search