Transformers as Recognizers of Formal Languages: A Survey on
  Expressivity
Lena Strobl William Merrill Gail Weiss David Chiang Dana Angluin
As transformers have gained prominence in natural language processing, some
researchers have investigated theoretically what problems they can and cannot
solve, by treating problems as formal languages. Exploring questions such as
this will help to compare transformers with other models, and transformer
variants with one another, for various tasks. Work in this subarea has made
considerable progress in recent years. Here, we undertake a comprehensive
survey of this work, documenting the diverse assumptions that underlie
different results and providing a unified framework for harmonizing seemingly
contradictory findings.