3 ms·
That's not a DFSM. DFSMs can't have ε-transitions. You need at least an ε-NFA for that. I think you also need to have at least one transition for every symbol
by duckerude 8y ago
That's not a DFSM. DFSMs can't have ε-transitions. You need at least an ε-NFA for that.
I think you also need to have at least one transition for every symbol in the alphabet from every state for it to be a valid ε-NFA, and then it can be reduced to a DFSM, giving it a bounded running time.
- jeromebaek 8y agoYou are correct, thank you for pointing it out. But my point still stands because there exists a bijection between DFAs and NFAs.
- duckerude 8y agoAny NFA can be reduced to a DFA (potentially at the cost of exponential blowup), and any DFA is also a NFA. That's not really a bijection, but it's true that they're equivalent. DFAs can run in bounded time, because every symbol takes exactly one step to be processed, and there is only one way to process a string. That also means NFAs can run in bounded time, by reducing them to DFAs first, but that's not a very satisfying explanation. A NFA rejects a string if it can not end in an accepting state. It's not intuitively straightforward to see whether that's the case, but it can be done in bounded time by exhaustively checking possible paths (which is possible with a finite number of states and a finite input string). You can't always perform that trick with Turing machines, because they can have infinitely many reachable states.