finding right quotient of languages 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. 
 A: 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:


*

*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$.

*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\}$.

*Say that $L_1 = \{\mathtt{carrot}\}$ and $L_2 = \{\mathtt{t}, \mathtt{ot}\}$. Then $\qq$ is $\{\mathtt{carro}, \mathtt{carr}\}$.

*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}\}$.

*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\}$.

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

*In general, if $L_2 = P\cup Q$, then $$\qq = (\Quot{L_1}P) \cup (\Quot{L_1}Q).$$

*In general, if $L_1 = P\cup Q$, then $$\qq = (\Quot P{L_2}) \cup (\Quot Q{L_2}).$$

*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.
