Repeat Exercise 4.5.1 for the grammar S -» 5 5 + | 5 5 * | a of Exercise 4.2.1 and the following right-sentential forms:  a) SSS + a*+.  b) SS + a*a+. c) aaa * a + +. Exercise 4.5.1 For the grammar 5...

Repeat Exercise 4.5.1 for the grammar S -» 5 5 + | 5 5 * | a of Exercise 4.2.1 and the following right-sentential forms:

a) SSS + a*+.

b) SS + a*a+.


c) aaa * a + +.

Exercise 4.5.1

For the grammar 5 -> 051|01o f Exercise 4.2.2(a), indicate the handle in each of the following right-sentential forms:

a) 000111.

b) 00511.

Exercise 4.2.2

Repeat Exercise 4.2.1 for each of the following grammars and strings:

a) S 0 5 1 | 0 1 with string 000111.


b) S + 5 5 | * S S | a with string + * aaa.

! c ) S S (S) S\e with string (()()).

! d ) S -> S + S\S S\(S)\S * \ a with string (a + a) * a.


! e ) S -» ( L ) | a and L -» L , 5 | 5 with string ((a ,a),a,(a)).


!! f) S -» a565|&5 , a5| e with string aabbab.

The following grammar for boolean expressions: bexpr -» 6e:rpr or fcierm | frterm ftterra —>• frterm and bfactor | bfactor bfactor -» no t bfactor | ( fcezpr) | true | false

Exercise 4.2.1

Consider the context-free grammar:


5 -> S S + \ S S * \ a

and the string aa + a*.

a) Give a leftmost derivation for the string.

b) Give a rightmost derivation for the string.

c) Give a parse tree for the string.

! d) Is the grammar ambiguous or unambiguous? Justify your answer.


! e) Describe the language generated by this grammar.