3 ms·
Even a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.
by unhammer 6y ago
Even 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.