CS21

A CFG grammar:
A → AA
A → (A)
A → ε
Proof that we always generate balanced expressions:
A → AA →* xy
by induction, xy is balanced if x and y are balanced
A → (A) →* (x)
by induction, (x) is balanced if x is balanced
Proof that any balanced expression can be represented by our grammar:
Consider the shortest prefix that is balanced:
1. if it is the whole string, it has a ( on the left and ) on the right
we can use the rule A → (A) →* (x)
2. otherwise
we can use the rule A → AA