While I was studying about Compiler Design it tells that we need 'finite automata' while designing a lexical analyzer like DFA or NFA. So I would like to know whether NFA is only used for conversion of (regular expressions to NFA and then to DFA). Is it possible to realize NFA practically? Or whether NFA is used because it is efficient than DFA?
Add a comment
|
1 Answer
Realizing an NFA in practice means backtracking, since your program flow cannot be in multiple different states simultaneously. (There are parallel processors, of course, but it's hard to map the irregular and chaotic behaviour of user-written regexes to the straightforward, regular data flow that vectorization units are designed for.) Therefore, for deciding a pure "Does this match?" question, it's almost always better to transform the NFA further into a DFA and run that. But NFAs are still used in practice because DFAs cannot do some things that users definitely want, such as capturing subgroups of an expression.
answered Nov 15, 2014 at 12:34
-
:thanks for your answer.But could you say what should I do to improve the question in programmers.stackexchange.com/questions/262865/… I have a doubt on this answer too but I would like to first know how NFA works with epsilon transition.– justinCommented Nov 17, 2014 at 8:32
-
That question would require a lot of information from the lecture slides pasted into it to be understandable. If I understand correctly, you're asking why you need the extra first and last states (9 and 10). As a matter of fact you could omit them, but then you'd have to assign the special 'start state' property to 7 and 'end state' to 8 instead. That is just an optimization that the standard algorithm doesn't make, presumably for the sake of simplicity. Commented Nov 17, 2014 at 8:37
-
:thanks for your comment.But could you say how it would be simple if we add two more states(9 and 10).I couldn't get what you meant by "sake of simplicity".– justinCommented Nov 17, 2014 at 8:43
-
The algorithm is simpler - it has fewer steps, because it doesn't need an extra "reduce redundant states" step. The output, of course, is bigger. It's often the case that generating smaller output requires a bigger algorithm - just think of compression. Commented Nov 17, 2014 at 8:45
-
:Does that mean that really there is no use in adding two states(9 and 10) other than simplifying the algorithm.– justinCommented Nov 17, 2014 at 8:49