3 ms·
The distinction is very practical. It's better to think about it in terms of hard-coded limits vs. arbitrary scaling than finite vs. infinite. Anything designed
by jltsiren 4y ago
The distinction is very practical. It's better to think about it in terms of hard-coded limits vs. arbitrary scaling than finite vs. infinite. Anything designed to handle n items needs "infinite" memory.
Language classes are about the code, not about the computer. With a finite state automaton, you have to commit to the size of the input in advance and write the state transitions explicitly. While there exist structurally similar automata that can handle larger inputs, your automaton – your code – cannot handle them. You can generate those automata algorithmically, but in order to do that, you need a more expressive formalism that can handle n items.