I am trying to prove by induction that if

$$\hat\delta_d(q_0, w) = \hat\delta_n(q_0, w)$$

I know by practicing inductive proofs of the $\hat\delta$ for DFAs, that on the basis of the definition of $\hat\delta_d$

  1. for any $q \in Q$, $\hat\delta(q, \epsilon) = q$

  2. for any $q \in Q$ and $a \in $ the language of the DFA, $\hat\delta(\delta(q, y), a)$

  3. $\hat\delta(q, ax) = \hat\delta(q_1, x)$ where $a_1 = \delta(q,a)$

Does the extended transition function also have these properties? Does it have other definitions/properties?

For reference, $\hat\delta_d$ refers to the extended transition function of DFAs and $\hat\delta_n$ refers to the extended transition function of NFAs.


closed as unclear what you're asking by Evil, David Richerby, Yuval Filmus, D.W. Feb 24 '18 at 6:54

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Kindly clarify what you mean specifically by $\hat\delta_d$,$\hat\delta_n$,$\hat\delta$. Are all of them transition functions for DFA's or does some of them refer to NFA's? $\endgroup$ – Sagnik Feb 23 '18 at 4:28
  • 2
    $\begingroup$ This question is unanswerable because you've not defined your notation and because you've only written half of what you're trying to prove: "If X=Y, then what?" You could attempt to prove that "If it is raining, sensible people use umbrellas" but it makes no sense to attempt to prove "If it is raining". $\endgroup$ – David Richerby Feb 23 '18 at 10:15
  • $\begingroup$ @DavidRicherby not trying to get help with the proof! Just trying to find properties of the extended transition function of NFAs. I mentioned the proof as context. If it is distracting, I will delete it. $\endgroup$ – maddie Feb 24 '18 at 5:23
  • $\begingroup$ Also, bullet 2 doesn't make any sense; something seems missing. Did you mean to say that $\hat{\delta}(\delta(q,y),a)$ is equal to something? If so, what? $\endgroup$ – D.W. Feb 24 '18 at 6:53
  • $\begingroup$ When you say the language of the DFA, do you perhaps mean the alphabet? ($\Sigma$) That's not the same thing. $\endgroup$ – D.W. Feb 24 '18 at 6:54