This is exercise 4.4.5 from purple dragon.
The grammar S -> aSa | aa generates all even-length strings of a's. We can
devise a recursive-descent parserwith backtrack for this grammar. If we choose
to expand by production S -> aa first, then we shall only recognize the string aa.
Thus, any reasonable recursive-descent parser will try S -> aSa first.
 
  a) Show that this recursive-descent parser recognizes inputs aa, aaaa, and
     aaaaaaaa, but not aaaaaa
!!b) What language does this recursive-descent parser recognize ?

VGhpcyBpcyBleGVyY2lzZSA0LjQuNSBmcm9tIHB1cnBsZSBkcmFnb24uClRoZSBncmFtbWFyIFMgLT4gYVNhIHwgYWEgZ2VuZXJhdGVzIGFsbCBldmVuLWxlbmd0aCBzdHJpbmdzIG9mIGEncy4gV2UgY2FuCmRldmlzZSBhIHJlY3Vyc2l2ZS1kZXNjZW50IHBhcnNlcndpdGggYmFja3RyYWNrIGZvciB0aGlzIGdyYW1tYXIuIElmIHdlIGNob29zZQp0byBleHBhbmQgYnkgcHJvZHVjdGlvbiBTIC0+IGFhIGZpcnN0LCB0aGVuIHdlIHNoYWxsIG9ubHkgcmVjb2duaXplIHRoZSBzdHJpbmcgYWEuClRodXMsIGFueSByZWFzb25hYmxlIHJlY3Vyc2l2ZS1kZXNjZW50IHBhcnNlciB3aWxsIHRyeSBTIC0+IGFTYSBmaXJzdC4KCiAgYSkgU2hvdyB0aGF0IHRoaXMgcmVjdXJzaXZlLWRlc2NlbnQgcGFyc2VyIHJlY29nbml6ZXMgaW5wdXRzIGFhLCBhYWFhLCBhbmQKICAgICBhYWFhYWFhYSwgYnV0IG5vdCBhYWFhYWEKISFiKSBXaGF0IGxhbmd1YWdlIGRvZXMgdGhpcyByZWN1cnNpdmUtZGVzY2VudCBwYXJzZXIgcmVjb2duaXplID8=