S  SS+ | SS* | a
a.) show how a string aa+a* can be generated by the grammar
b.) construct a parse tree for this string.
c.) what language is generated by this language

S

SS*
Sa*
SS+a*
aa+a*



a language that accepts a string with a minimum value of “a” and may also contain an infinite amount of a’s, +’s and *’s.

2.2

a.) S  0S1 | 01
A language that accepts a string which has equal numbers of 0s and 1s where the 0s precede the 1s, with the minimum value of 0011.

b.) S+SS| -SS| a


c.) SS(S)S|Є
A language that accepts a string which may contain an infinite number of S’s and may contain a minimum value of SS.

d.) SaSbS| bSaS| Є
A language that accepts a string which contains an equal number of a’s and b’s and which could contain a minimum value of one “a” and one “b”.

e.) S a| S+S| SS| S*| (S)
A language that accepts a string which contains a minimum value of “a” and may contain an infinite amount of a’s, +’s and *’s.

2.3
The language in letter e is ambiguous.



2.4)

Construct an unambiguous context-free grammar for each of the following languages. In each case show that your grammar is correct.