3 ms·
Not if it's bounded on memory. A memory-bounded pushdown automaton will also fail but a general computer can match it. For the post I was referring to the phys
by kevmo314 6y ago
Not if it's bounded on memory. A memory-bounded pushdown automaton will also fail but a general computer can match it.
For the post I was referring to the physical computers we work with daily. I should clarify :)
- unhammer 6y agoEven a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.
- kevmo314 6y agoThe point I'm trying to make is not that FSM actually can do these, but rather that this distinction is largely theoretical. In practice, even linearly bounded isn't practical because of course I can pick a sufficiently large input that will run out of tape: there's only so much information storage in the universe.