Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It is an NFA in every way except that you no longer have a single list of accepting states. "Doing two different things simultaneously" is the whole concept of nondeterminism.

If you loosen the definition of "NFA" that you're working with from requiring a set of final states to requiring a function from a set of states to {0, 1}, everything will still work exactly the same way, all of your theorems will still hold, but intersecting two NFAs will consist of adding one state and adjusting the accept function.



> It is an NFA in every way except

So not an NFA. That's fine, you can always define "extended NFAs", and some variants are practically useful. For example, most practical "regex" implementations have features like backreferences that are very convenient, but strictly more powerful than DFAs. You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.


> You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.

As I explicitly observed above:

>> everything will still work exactly the same way, all of your theorems will still hold

you don't lose any of the established theory by doing this.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: