Exercises

2.1 Consider the context-free grammar: S -> S S + | S S * | a

a.) Show how the string aa+a* can be generated by this grammar.
S -> S S *
S -> S S + S *
S -> a S + S *
S -> a a + S *
S -> a a + a *

b.) Construct a parse tree for this string.


c.) What language is generated by this grammar? Justify your answer.
Supposing a is an identifier for a numeric value, then the grammar generates a language which is composed of all possible arithmetic combinations of a using the operations + and * and postfix notation.

2.2 What language is generated by the following grammars? In each case, justify your answer.

a.) S -> 0 S 1 | 0 1
A language that generates a series of equal numbers of 0's and 1's, where the sequence of 0's precedes the sequence of 1's.

b.) S -> + S S | - S S | a
A language consisting of all possible arithmetic combinations of a using only the operations + and * and prefix notation. This is actually the prefix analog to exercise 2.1

c.) S -> S ( S ) S | €
A language that generates a string starting with S and ending with S, where there is an even number of S's and where the leftmost half (which starts with a S and ends with an opening parenthesis) of the string is composed of alternating S's and opening parentheses and the rightmost half (which starts with a closing parenthesis and ends with an S) of the string is composed of alternating closing parentheses and S's. In other words, this will simply generate arbitrary sequences of adjacent and nested, matched pairs of parentheses.

d.) S -> a S b S | b S a S | €
A language that generates a string which is composed of equal numbers of a's and b's in any or no particular order.

e.) S -> a | S + S | S S | S * | ( S )
A language that generates a string composed of any number of a's separated by mathematical operations(addition and multiplication) and/or parentheses in particular.