0
$\begingroup$

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?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ What is the question? All I see is a copy-paste of an exam question and a grammar (and one that is formatted so poorly that it is hard to read), but no question about that exercise/grammar. I suggest you read our reference question cs.stackexchange.com/q/11315/755 and study the methods there and spend a few hours trying to solve it on your own, then see if you have any remaining question, and if so, edit the question to ask a specific, answerable question, and show us what you tried and what your thoughts are. See also cs.stackexchange.com/help/how-to-ask. $\endgroup$ – D.W.♦ Nov 30 '15 at 6:46
  • $\begingroup$ @D.W. that proof you linked me to shows how to do a proof when the langauge and grammar are both given. On my test there was no language. We were to derive the language L from the Grammar G and then use the induction to prove it. $\endgroup$ – chamburger Nov 30 '15 at 15:18
  • 1
    $\begingroup$ Finding the language is the easy part. You just have to think a little. $\endgroup$ – Renato Sanhueza Nov 30 '15 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.