World's most popular travel blog for travel bloggers.

[Solved]: Show how a sentence can be produced from a grammar (Dragon book 2.1)

, , No Comments
Problem Detail: 

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.

Asked By : dan

Answered By : pyguy

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9109

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback