Can´t find anything affirmative about it. And a NFA with any epsilon transition is a epsilon-NFA ? Thanks.
Asked
Active
Viewed 3.1k times
13
-
What do you mean by lambda transition? – Bhushan Firake Dec 09 '12 at 20:03
-
Some books use lambda instead of epsilon. It's the same thing. – liwing Dec 09 '12 at 20:05
4 Answers
23
DFA doesn't have epsilon transitions.If it had it, it could transit from current state to other state without any input i.e. with nothing , not even {} or phi. And as definition , we know that the input must be from the input set. Hope this cleared your doubt ...
Bhushan Firake
- 9,338
- 5
- 44
- 79
-
What if this transition was to a final state ? Like figure 3.51 in page 225 of this document http://www.univasf.edu.br/~marcus.ramos/lfa-2008-1/Secao%2003-06.pdf . – liwing Dec 09 '12 at 20:11
-
Wow..the image is self-explanatory now..as you see, q0 transits to q3 without any input and hence it is NFA and it has epsilon moves so it is epsilon-NFA and not the DFA.. – Bhushan Firake Dec 09 '12 at 20:15
5
From the definition of DFA ,"Deterministic Finite Automata is a machine that can't move on other state without getting any input".And since epsilon means nothing.Hence DFA can't move on epsilon moves.
Whereas from the definition of NFA,"Non deterministic Finite Automata is a machine that may move on other state without getting any input".So NFA can move on epsilon moves.
SARIKA KESHRI
- 51
- 1
- 2
3
DFA must have a definite input symbol to move from one state to another state. Epsilon move isn't allow in DFA, because it'll change DFA into NFA. For e.g., suppose you are in state Q1, and you have a transition (Q1, e) = Q2, in this case you can directly go to Q2 without apply any input or you can stay in Q1 state, so you have two choosing opportunity at state Q1. In case of DFA you mustn't have any choosing criteria. That's why DFA don't have epsilon moves.
noNameYet
- 635
- 2
- 10
- 15
0
If the start state is also an end state then the fa accepts lamda. Also, if the fa specifically shows a transition from one state to the next with lamda then lamda can be considered an input.
bad_coder
- 11,289
- 20
- 44
- 72
