How to find the right quotient of a language given two languages?

Question

If $L_1= \{a^n b^m \mid n \geqslant 1, m \geqslant 1 \} \cup \{ba\}$ and $L_2= \{b^m \mid m \geqslant 0 \}$.

I am not getting how the DFA for $L_1/L_2$ is constructed in the second figure using the DFA for $L_1$, please tell me the approach.

Answer 1

First of all, a small correction. The language accepted by the automaton in Figure 4.1 is $$ L_1 = \{a^nb^m \mid n \geqslant 1, m \geqslant 0 \} \cup \{ba\} = a^+b^* \cup \{ba\} $$ Now, if $L_2 = b^*$, then $$ L_1/L_2 = \{ u \in A^* \mid \text{there exists $n \geqslant 0$ such that $ub^n \in L_1$} \} $$ I claim that $L_1/L_2 = L_1$. Indeed, if $u \in L_1$, then $ub^0 \in L_1$ and $b^0 \in L_2$ so that $u \in L_1/L_2$. Conversely, if $u \in L_1/L_2$, then $ub^n \in L_1$ for some $n \geqslant 0$. It follows that either $u = ba$ or $u \in a^+b^*$ and thus $u \in L_1$ in both cases.

Consequently, the answer in Figure 4.2 is incorrect (unless you also made a mistake in the definition of $L_2$).