Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
3  
@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

3 Answers 3

up vote 4 down vote accepted

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$.
share|improve this answer
1  
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$.

share|improve this answer
    
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.