Transformers have supplanted recurrent models in a large number of NLP tasks.
However, the differences in their abilities to model different syntactic
properties remain largely unknown. Past works suggest that LSTMs generalize
very well on regular languages and have close connections with counter
languages. In this work, we systematically study the ability of Transformers to
model such languages as well as the role of its individual components in doing
so. We first provide a construction of Transformers for a subclass of counter
languages, including well-studied languages such as n-ary Boolean Expressions,
Dyck-1, and its generalizations. In experiments, we find that Transformers do
well on this subclass, and their learned mechanism strongly correlates with our
construction. Perhaps surprisingly, in contrast to LSTMs, Transformers do well
only on a subset of regular languages with degrading performance as we make
languages more complex according to a well-known measure of complexity. Our
analysis also provides insights on the role of self-attention mechanism in
modeling certain behaviors and the influence of positional encoding schemes on
the learning and generalization abilities of the model.

本文系统研究了 Transformers 模型在模拟正则语言和反计数语言中的能力，并探讨了其中各组件的作用，发现相比于 LSTMs，在某些行为建模上有一定优势，同时也揭示了自我注意机制和位置编码对模型学习和泛化能力的影响。