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?

  • $\begingroup$ 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? $\endgroup$
    – Berci
    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.

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

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.