alt Hacker NewsThis is very interesting since there is another notable paper which shows LLMs can recognize and generate CFGs
https://arxiv.org/abs/2305.13673
and of course a^n b^n is also classic CFG, so it's not clear why one paper had positive results while the other hand negative.
Dyck grammar (balanced brackets) are not an a^nb^n, there are several kinds of brackets.
I cannot find probability of success in paper you linked. Is it 100%? I believe it is less than 100%, because LLMs are intrinsically probabilistic machines.