Question 62

Analyze DFA $M$:

• Start state $q_0$, accepting state $q_1$.
• Any string ending with symbol $a$ transitions to $q_1$, while any string ending with $b$ transitions to $q_0$.
• Hence, $L(M) = \{w \in \{a, b\}^+ \mid w \text{ ends in } a\}$.

Analyze DFA $N$:

• Start state $p_0$, accepting state $p_1$.
• Any string ending with symbol $b$ transitions to $p_1$, while any string ending with $a$ transitions to $p_0$.
• Hence, $L(N) = \{w \in \{a, b\}^+ \mid w \text{ ends in } b\}$.

Intersection language $L(M) \cap L(N)$:

• A string cannot end simultaneously in $a$ and in $b$.
• Thus, $L(M) \cap L(N) = \emptyset$ (the empty language).

Minimal DFA for the empty language:

• A DFA over alphabet $\{a, b\}$ that accepts $\emptyset$ requires only a single non-accepting state with self-loops on both $a$ and $b$.
• Hence, the minimal DFA contains exactly $1$ state.