A completely uniform transformer for parity

One of the ways to do mathematical analysis of the capabilities and limitations of the transformer architecture [8] is to study formal languages, recognizable by them. Namely, for a given formal language L, we study, if there exists a choice of parameters in the transformer architecture, for which words from L are accepted and words not from L are rejected by the resulting transformer. A seminal work of Hahn [5] performed such analysis for a number of formal languages, including the parity language, consisting of binary words with even number of 1s. Hahn have shown that transformers, recognizing this language, must have low confidence, partially explaining an empirically observed struggle of transformers in learning this language [1, 4]. However, this does not exclude the possibility of existence of a theoretical solution for this language.