extended transition function for NFAs

Question

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?

Answer 1

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.