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.
Asked
Active
Viewed 910 times
1 Answers
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$).
J.-E. Pin
- 40,163
-
There is a mistake in the definition of $L_2$ in the original question. In the book it is given $L_2={m^m|m>=1}$. If this is the case then $L_1/L_2$ cannot contain $ba$, right? Also this means, $L_1|L_2 \neq L_1$, right? Then in that case figure. 2 could be right answer. ... – Mahesha999 May 17 '15 at 09:16
-
... However, I see figure 2 is ill constructed, since there is no label on edge from $q_2$ to $q_5$. Also I want to know, if $q_1$ and $q_2$ are the only accepting states, then can we simply eliminate $q_3,q_4,q_5$ since they do not transit to $q_1,q_2$? Or we need to do subset construction for dfa state reduction? – Mahesha999 May 17 '15 at 09:16
-
If $L_2= b^+$, then Figure 2 is correct. You can merge state the states $q_3$, $q_4$ and $q_5$ if you want to have a complete automaton and eliminate them if you accept incomplete automata. – J.-E. Pin May 17 '15 at 09:51
-
What is the significance of complete automaton when those states$q_3,q_4,q_5$ will not contribute to acceptance of any string? Also that missing label on transition is mistake right? – Mahesha999 May 17 '15 at 10:29