0
$\begingroup$

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

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

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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