Copy Automata as a Diagnostic Tool for Pattern-Copying in Transformers: Hierarchy, Bounds, and the Limits of Hard-Attention Theory

We study pattern copying in Transformers through Copy Automata, deterministic finite automata equipped with a copy output function, used as a diagnostic abstraction rather than a predictive theory We establish three results: an Encoding Theorem for bounded-precision Transformers, a Hard-Attention Separation Theorem giving task-specific head-count requirements, and a counting bound for level-k identification Empirically, small-scale and GPT-2-scale experiments show that Level-3 context-dependent bijections remain the hardest case Five probes, covering gradients, non-gradient solvers, structured mappings, capacity scaling, and induction-score recovery, suggest that Level-3 failure is better explained by a combination of soft-attention capacity mismatch and optimisation difficulty than by raw hard-attention capacity alone We summarise this gap with a soft-attention capacity-discount heuristic The main contribution is a diagnostic account of where hard-attention theory breaks down for softmax Transformers.