finding right quotient of languages

Question

Can someone enumerate in detail, the steps to find right quotient of languages, i.e. $L_1/L_2$. Using an example will be great.

Answer 1

The right quotient of $L_1$ with $L_2$ is the set of all strings $x$ where you can pick some element $y$ from $L_2$ and append it to $x$ to get something from $L_1$. That is, $x$ is in the quotient if there is $y$ in $L_2$ for which $xy$ is in $L_1$.

Let's agree to write the quotient of $L_1$ by $L_2$ as $\def\Q{\operatorname{Quotient}}\def\Quot#1#2{{#1}/{#2}}\def\qq{\Quot{L_1}{L_2}}\qq$.

Here are some examples:

1. Say that $L_1$ is the language $\{\mathtt{fish}, \mathtt{dog}, \mathtt{carrot}\}$ and that $L_2$ is the language $\{\mathtt{rot}\}$. Then $\qq$, the quotient of $L_1$ by $L_2$, is the language $\{\mathtt{car}\}$, because $\mathtt{car}$ is the only string for which you can append something from $L_2$ to get something from $L_1$.
2. Say that $L_1$ is the language $\{\mathtt{carrot}, \mathtt{parrot}, \mathtt{rot}\}$ and that $L_2$ is the language $\{\mathtt{rot}\}$. Then $\qq$ is the language $\{\mathtt{car}, \mathtt{par}, \epsilon\}$. Say that $L_3 = \{\mathtt{rot}, \mathtt{cheese}\}$. Then $\Quot{L_1}{L_3}$ is also $\{\mathtt{car}, \mathtt{par}, \epsilon\}$.
3. Say that $L_1 = \{\mathtt{carrot}\}$ and $L_2 = \{\mathtt{t}, \mathtt{ot}\}$. Then $\qq$ is $\{\mathtt{carro}, \mathtt{carr}\}$.
4. Say that $L_1 = \{\mathtt{xab}, \mathtt{yab}\}$ and $L_2 = \{\mathtt{b}, \mathtt{ab}\}$. Then $\qq$ is $\{\mathtt{xa},\mathtt{ya},\mathtt{x},\mathtt{y}\}$.

5. Say that $L_1 = \{\epsilon, \mathtt{a}, \mathtt{ab}, \mathtt{aba}, \mathtt{abab}, \ldots\}$ and $L_2 = \{\mathtt b, \mathtt{bb}, \mathtt{bbb}, \ldots\}$. Then $\qq$ is $ \{\mathtt a, \mathtt{aba}, \mathtt{ababa}, \ldots\}$.

6. In general, if $L_2$ contains $\epsilon$, then $\qq$ will contain $L_1$.

7. In general, if $L_2 = P\cup Q$, then $$\qq = (\Quot{L_1}P) \cup (\Quot{L_1}Q).$$
8. In general, if $L_1 = P\cup Q$, then $$\qq = (\Quot P{L_2}) \cup (\Quot Q{L_2}).$$
9. The two foregoing facts mean that you can calculate the right quotient of two languages $L_1$ and $L_2$ as follows: Let $s_1$ be some element of $L_1$ and let $s_2$ be some element of $L_2$. If $s_2$ is a suffix of $s_1$, so that $s_1 = xs_2$ for some string $x$, then $x$ is in the quotient $L_1/L_2$. Repeat this for every possible choice of $s_1$ and $s_2$ and you will have found every element of $L_1/L_2$.

I hope this is some help.