Timeline for Advantages/Disadvantages of NFA over DFA and vice versa
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2021 at 3:00 | history | tweeted | twitter.com/StackSoftEng/status/1345565565927239683 | ||
| May 11, 2011 at 22:46 | history | edited | Jonas |
edited tags
|
|
| May 11, 2011 at 22:44 | comment | added | Jonas | This sounds like a question for CSTheory.stackexchange.com | |
| May 11, 2011 at 22:03 | comment | added | user8709 | NFAs aren't necessarily slower. The logic to execute them is a tad more complex, but the large number of states for an equivalent DFA can mean that memory bandwidth becomes an issue. Organising a state table to optimise locality of accesses is, I expect, very difficult. So the slightly more complex code for NFAs is a trade-off against memory usage which may well pay off with faster run-times, at least in principle, though I've not looked up any real-world benchmarks. | |
| May 11, 2011 at 21:45 | answer | added | user8709 | timeline score: 6 | |
| May 11, 2011 at 19:52 | answer | added | btilly | timeline score: 3 | |
| May 11, 2011 at 19:41 | comment | added | David Thornley | The big advantage of NFAs is that they can search much faster; the big advantage of DFAs is that they are physically possible. Or were you referring to some sort of implementation? | |
| May 11, 2011 at 19:31 | answer | added | DXM | timeline score: 2 | |
| May 11, 2011 at 19:27 | history | asked | user23871 | CC BY-SA 3.0 |