[Math] How to compute the transition function in non-determinism finite accepter NFA

automatacomputer science

I'm currently teaching myself Automaton using Peter Linz book – An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51):
enter image description here

According to the author, the transition function $$\delta^{*}(q_1,a) = \{q_0, q_1, q_2\}$$, and I have no idea how this works since the definition is defined in the book as following:

For an nfa, the extended transition function is defined so that $\delta^{*}(q_i,w)$ contains $q_j$ if and only if there is a walk in the transition graph from $q_i$ to $q_j$ labeled $w$. This holds for all $q_i, q_j \in Q$ and $w \in \sum^{*}.$

From my understanding, there must be a walk of label $a$ so that a state $q_k$ will be in the set. In the example above, there is no such walk label $a$ from $q_1$ to $q_0, q_2$. Perhaps, I missed some important points, but I honestly don't understand how the author got that answer, i.e. $\{q_0, q_1, q_2\}$. Any suggestion?

Thank you,

Note I already posted this question as I already posted my question at https://cstheory.stackexchange.com/questions/7009/how-to-compute-the-transition-function-in-non-determinism-finite-accepter-nfa. However, it was closed because it's not at graduate research level.

Best Answer

I think you are just missing that $\lambda$ is a common notation for the empty word (I prefer $\varepsilon$, but still…). The NFA you reported is in fact an NFA with $\varepsilon$-moves. Hence there are paths labeled $a$ from $q_1$ to any state:

  • to get to $q_0$, you just need to follow $\lambda\lambda a\lambda\lambda=a$,
  • for $q_1$, follow $\lambda\lambda a=a$, and
  • for $q_2$, follow $\lambda\lambda a\lambda=a$.
Related Question