# How to compute the transition function in non-determinism finite accepter NFA?

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):

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 http://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.

-
I would assume that it's wrong unless $\lambda$ corresponds to some pathological transition. Nevertheless, I've never seen such pathological transitions and I will call the automaton on your picture deterministic. – Ilya Jun 15 '11 at 14:36
@Gortaur: $\lambda$ is the 'empty' transition, and it labels the transitions from $q_1$ to $q_2$ and $q_2$ to $q_0$. – Mitch Jun 15 '11 at 15:32
@Gotaur: Deterministic FAs may not have $\lambda$ transitions. This is an NFA, sometimes called an NFA-$\lambda$ since the $\lambda$ transitions is the only thing keeping it from being an FA. – kba Jun 15 '11 at 16:24
@Mitch, Kristian: thanks. – Ilya Jun 15 '11 at 17:49

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$.
-
Thanks a lot ;) – Chan Jun 15 '11 at 15:53

Transitions on labels $\lambda$ ($\epsilon$ is another label for the 'null' transition) are weird. They can be followed without input. Once you compute the functional input of '$a$' using $\delta^*$, you have to follow all the $\lambda$$transitions as far as they can go. If you're at$q_1$, you're really also already at$q_2$and$q_0$. Then on input of$a$, you implicitly move from$q_0$to$q_1$and then implicitly you're also again moving to$q_2$and also$q_0\$.

-
Thanks for the explanation. I kinda see it now. – Chan Jun 15 '11 at 15:54

be careful that your machine should read 'a' to accept destination state. in your nfa, before reading 'a', 2 lambda transitions should be placed. first, to go to q2, and second, to go to q0. after that your machine can read a 'a' and places on q1. now transition to q2 and q0 are take placed by one and two lambda transitions. good luck

-