  Transformer-based language models are effective but complex, and
understanding their inner workings is a significant challenge. Previous
research has primarily explored how these models handle simple tasks like name
copying or selection, and we extend this by investigating how these models
grasp complex, recursive language structures defined by context-free grammars
(CFGs). We introduce a family of synthetic CFGs that produce hierarchical
rules, capable of generating lengthy sentences (e.g., hundreds of tokens) that
are locally ambiguous and require dynamic programming to parse. Despite this
complexity, we demonstrate that generative models like GPT can accurately learn
this CFG language and generate sentences based on it. We explore the model's
internals, revealing that its hidden states precisely capture the structure of
CFGs, and its attention patterns resemble the information passing in a dynamic
programming algorithm.
  This paper also presents several corollaries, including showing why
positional embedding is inferior to relative attention or rotary embedding;
demonstrating that encoder-based models (e.g., BERT, deBERTa) cannot learn very
deeply nested CFGs as effectively as generative models (e.g., GPT); and
highlighting the necessity of adding structural and syntactic errors to the
pretraining data to make the model more robust to corrupted language prefixes.
