Chapter 2 Exercises

2.1 Consider the following context-free grammar

S -> S S + S S * a

a. show how the string aa+a* can be generated by this grammar.

ans: S -> SS*
Sa*
SS+ a *
a a + a *

b. Constuct a parse tree for this string

ans:
S
/ \
S S *
/ \
S S + a

a a

c. What language is generated by this grammar? Justify you answer

ans: The language defined by this grammar consists of two (2) consecutive a separated by plus and minus signs.


2.2 What language is generated by the following grammar? In each case justify you answer.

a. S -> 0 S 1 0 1

The language that is generated by this gramma is compose of digits number one (1) and zero (0).


b. S -> + S S - S S a

The language that is generated by this grammar is compose of a's separated by plus and minus signs.

c. S -> S ( S ) S є

The language that is generated by this grammar is compose of є.

d. S -> a S b S b S a S є

The language that is generated by this grammar is compose of a, b, and є.


e. S -> a S + S S S S * ( S )

The language that is generated by this grammar is compose of infinite consecutive S with plus (+) and * signs.

2.3