Problem: The grammar S a Sala a generates all even-length strings of a's. We can devise a recursive-descent parser with backtrack for this grammar. If we choose to expand by production Sa a first, then we shall only recognize the string aa. Thus, any reasonable recursive descent parser will try Sa Sa first.
a) Show that this recursive-descent parser recognizes inputs aa, aaaa, and aaaaaaaa, but not aaaaaa.