3 ms·
If there is a finite input it is regular.
by charcircuit 4y ago
If there is a finite input it is regular.
- smadge 4y agoAs in you construct a FSM that can recognize all strings of a context free language less than a certain length?
- deleted 4y ago[deleted]
- Kranar 4y agoYou might mean something like if you restrict the set of all valid inputs to N characters then the language is regular, but that's a much stronger condition than requiring the input to be finite. Furthermore, such a restriction makes the language non-recursive; it's effectively a trivial language. In standard automata theory, all inputs to automatons are finite.
- charcircuit 4y agoYes, I was hoping people would understand that from the context.
- cma 4y agoThe paper covers that. They only test to a finite size, but the models that fail can't generalize significantly beyond the size of explicit examples they were trained on. Formally transformers should be capable of modeling it with the right weights, but they show good evidence those weights can't be learned with gradient descent. Whereas a neural turing machine or stack machine can learn them with gradient descent.