How do you prove two languages are equivalent using the definition of acceptance?

Question

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ and

$\delta'(q,a) = \begin{cases} \delta (q,a) & \text{if }q\in Q\\ \delta (q_0,a) & \text{if }q= q_f. \end{cases}$

I'm assuming I need to use induction but I'm not sure how to go about it

Answer 1

I don't think you need to use induction, a simpler case analysis will suffice, along with a couple of central observations about the new DFA $f(M)$:

1. $q_{f}$ is the new start state,
2. $q_{f}$ is also an accepting state,
3. $\delta'$ is almost exactly the same as $\delta$ (in a very specific way of course), and
4. there's no transitions into $q_{f}$.

From this you can argue what happens on input $x$ in two cases:

1. $x = \varepsilon$, and
2. $x$ is anything else.