Transformers are able to recognize balanced brackets grammar at 97% success rate: https://openreview.net/pdf?id=kaILSVAspn
replyThis is 3% or infinitely far away from the perfect tech.
The perfect tech is the stack.
This is very interesting since there is another notable paper which shows LLMs can recognize and generate CFGs
replyhttps://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.
replyI 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.