Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get.

Chapter 2, Exercies: 2.1
Given the context-free grammar $$S \to S S + \mid S S * \mid a$$ Task: Show how the signs aa+a* can be produced from this grammar.

I understand the grammar, $S$ can have the form $S S +$… and so on. But I don't know what I'm supposed to do in this task. Sadly I can't find any solutions on the web.

share|improve this question

migrated from cstheory.stackexchange.com Jan 23 '13 at 15:19

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer 1

up vote 4 down vote accepted

$$\begin{align*} S \Rightarrow & SS* \\ \Rightarrow & SS+S* & \text{(leftmost derivation )} \\ \Rightarrow & aS+S* \\ \Rightarrow & aa+S* \\ \Rightarrow & aa+a* \\ \end{align*}$$

share|improve this answer
excellent, thank you! –  dan Jan 23 '13 at 15:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.