I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction.
$$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \mid b \\ \end{align}$$
I got this wrong on my test and my professor isn't explaining why. Just references the pdf notes he gave us. My answer was very incomplete as when I created parse trees to figure out a pattern for the language I came to the conclusion that a word can either have all or none both a and b. And I couldn't find any real pattern. I didn't even get to the proof part of the question and I was hoping someone might be able to direct me in the right direction.
With the help of Rick Decker, I got as far as seeing the language was (a+b)* but was not sure how to proceed. So by choosing a w of an arbitrary length n that is greater than 0, if we take a string and add it to the prefix of z to get zb or za, and z is an element of L than the proof holds from the derivation? How do you come up with the derivation? Does that require a proof?
