With a TCS point view towards computability, we don't care about the exact constant.
Transformers cannot recognize certain simple regular languages like finite group mul, at a given depth.
exp(c|S|) is more like a loose bound for the proof and might be smaller in practice.
