Fixed-depth hard attention cannot recognize PARITY or 2DYCK

Let the model have $L$ layers and let $N=n+1$ be the number of input positions for a word of length $n$, including its fixed end marker. Initially each free layer-zero state depends on its own input symbol. For all sufficiently large $n$, at least $0.99N$ positions are free, since only the end-marker position is fixed. Apply [F1] successively through the $L$ layers, using free fractions $0.99=C_0>C_1>\cdots >C_L=0.9$. For every sufficiently large $n$, this gives a restriction leaving at least $0.9N$ free word positions and a constant $c_L$ such that the classification output depends on at most $c_L$ input positions.

Now suppose the model recognizes $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$. Its restriction to the two-symbol subalphabet consisting of one opening bracket and its matching closing bracket would recognize the one-type Dyck language, whose words have equal numbers of opening and closing brackets and nonnegative opening-minus-closing count at every prefix. Fix an even word length $n$, put $N=n+1$, and let $m=\lfloor n\mathrm{/}5\rfloor$. Initially fix the first $m$ word symbols to the opening bracket and the last $m$ word symbols to the closing bracket; leave the middle symbols free and keep the end marker fixed. For all sufficiently large even $n$, at least $0.59N$ positions are free. By [F1], with final free fraction $0.55$, refine this restriction so the model output depends on at most $c_L$ input positions and at least $0.55N$ word positions remain free. If $t$ middle positions were additionally fixed, then $t\le n-2m-0.55N\le 0.06N$ for all sufficiently large $N$. Also $m\ge N\mathrm{/}5-6\mathrm{/}5$, so $m>t$.

Choose $n$ large enough that $0.9N>c_L$. Some free bit position $i$ is not among the at most $c_L$ positions determining the output. Complete the restriction arbitrarily to a word $w$, and let $w^{\mathrm{\prime }}$ be obtained by flipping bit $i$. Their model outputs agree because all input positions on which the output depends agree, but exactly one of $w,w^{\mathrm{\prime }}$ has an even number of ones. Thus no such model classifies all length-$n$ words exactly as $\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{I}\mathrm{T}\mathrm{Y}$.

Let $f_o$ be the number of additionally fixed middle symbols that are opening brackets, and let $M=n-2m-t$ be the number of still-free middle positions. Assign an opening bracket to the first $r=n\mathrm{/}2-m-f_o$ still-free positions in their order, and assign a closing bracket to the rest. Since $m+t<n\mathrm{/}2$, we have $r\ge 0$ and $M-r=n\mathrm{/}2-m-t+f_o>0.$ The completed word has exactly $n\mathrm{/}2$ opening brackets, hence total balance zero. A prefix before the last of the assigned free opening brackets has height at least $m-t>0$, because at most $t$ fixed middle symbols are closings. After that last free opening, every still-free middle symbol is a closing. For any later prefix ending in the middle segment, its remaining suffix contains the final $m$ fixed closings and at most $t$ fixed openings, so its net opening-minus-closing count is at most $t-m<0$. Since the whole word has total balance zero, every such middle prefix has positive height. The final $m$ closing brackets decrease the height from $m$ to zero. Thus this completion is a valid one-type Dyck word.

At least $0.55N$ positions remain free, so for sufficiently large $n$ there is a free word position $i$ outside the at most $c_L$ positions determining the model output. Flip its bracket in the valid completion from step 2.2. The new word is unbalanced, while the model output is unchanged because position $i$ does not affect that output. This contradicts recognition of the one-type Dyck language. Any exact recognizer for $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$ would restrict to an exact recognizer for this one-type sublanguage, so no such hard-attention model recognizes $2\mathrm{D}\mathrm{Y}\mathrm{C}\mathrm{K}$.