# extended transition function for NFAs

Below I am using a DFA transition function that is extended to accept words instead of just symbols. Let's say it is given that the following information is true:

$$\delta(q_0, 0^3) = \delta(q_0, 0^6)$$

Using this information it can easily be proven that:

$$\delta(q_0, 0^6) = \delta(q_0, 0^{15})$$

is also true.

However let's say we have the same information about a NFA and not a DFA, so that in a NFA we know that the following is true:

$$\delta(q_0, 0^3) = \delta(q_0, 0^6)$$

The question is:

Given that I cannot extend the transition function to accept words in an NFA, (because in an NFA the transition function produces a set)

how do I go about proving that

$$\delta(q_0, 0^6) = \delta(q_0, 0^{15})$$

must also hold true for this NFA?

Is defining a new transition function that takes a set of states and a word and returns another set good way to do so?

• I don't understand why NFA is a problem. It has the same expressiveness as DFA. Why can't you convert the NFA to a corresponding DFA, and then do it. Commented May 20, 2015 at 20:58
• This is usually considered a bad question because you already know what to do, and there is not much to discuss. The answer is YES, but it is too short and the system will not accept it. The transition function is to be extended in the standard way to sets of states. Actually, using sets (of states, or of configurations) is one common way to do proofs with non-determinism. Raise your head and have faith in yourself. Commented May 20, 2015 at 21:09
• Actually, doing this extension is necessary when you want to define the application of the transition function to a string rather than a single symbol. Doing without it is possible, but so tedious and painful. Commented May 20, 2015 at 21:39

For an NFA $$A = (\Sigma, Q, Q_0, \delta, F)$$, we can extend the transition function $$\delta$$ to sets of states and finite words in the expected way: $$\delta: 2^Q\times \Sigma^* \to 2^Q$$ is such that for every $$S \in 2^Q$$, finite word $$u\in \Sigma^*$$, and letter $$\sigma\in \Sigma$$, we have that $$\delta(S, \epsilon) = S$$, $$\delta(S, \sigma) = \bigcup\limits_{s\in S}\delta(s, \sigma)$$, and $$\delta(S, u \cdot \sigma) = \delta(\delta(S, u), \sigma)$$. In words, $$\delta(S, u)$$ is the set of states that $$A$$ may reach when it reads the word $$u$$ from some state in $$S$$.
As is the case with deterministic automata, it is easy to prove by induction that $$\delta(S, u\cdot v) = \delta(\delta(S, u), v)$$, for any words $$u$$ and $$v$$. Another way to think about the extended $$\delta$$ is as the extended transition function of the equivalent DFA that we got upon applying the powerset-construction on $$A$$. So the short answer to your question is yes.