# DFA Transition Function Inductive Proof

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?

• Isn't it just a recursive definition of the extension $\hat\delta$ of $\delta$ to input whole strings as well? If not, how do you define this 'transitive closure' in this context? Nov 3 '13 at 23:42

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.
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)$.