1
$\begingroup$

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.

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