3 ms·
> any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string). This is wrong.
by jeromebaek 8y ago
> any particular DFSM has bounded memory use (based on the number of states) and bounded running time (based on the length of the input string).
This is wrong. This DFSM does not halt: node with arrow pointing back to the node on empty input.
- duckerude 8y agoThat'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.