log in

CS21 notes

Luke Breuer
2010-01-13 21:36 UTC

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