[Math] DFA Transition Function Inductive Proof

automataformal-languagesinduction

Show for any state $q$, string $x$, and input symbol $a$, $\hat\delta(q, ax) = \hat\delta(\delta(q, a), x)$, where $\hat\delta$ is the transitive closure of $\delta$, which is the transition function for some DFA.

I think the best way to proceed is by induction and that the following is the basis step:

Basis: $\hat\delta(q, a) = \hat\delta(\delta(q, a), \epsilon)$

But I am not sure how to proceed to the inductive step as I'm a little unsure how to use induction in these cases: it seems much different from numerical induction. Can someone provide a suggestion?

Best Answer

I think, $\hat\delta$ is not 'transitive closure', at least not as it is meant among relations, rather it is just an extension of $\delta$ to input also strings not just characters.

And it seems that it is just the recursive definition of this, so nothing to prove.

  1. Let $\hat\delta(q,\varepsilon):=q$.
  2. If it is already defined on word $x$ with all states, then let $\hat\delta(q,ax):=\hat\delta(\delta(q,a),x)$.
Related Question