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

  • $\begingroup$ Is $q_{0}$ the original start state? $\endgroup$ Commented Feb 11, 2015 at 5:03
  • $\begingroup$ For grammars, see our reference question. The technique may carry over, somewhat. $\endgroup$
    – Raphael
    Commented Feb 11, 2015 at 8:33

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.