Assignment 3 

3.1

Consider the grammar 

     S ::= ( L ) | a
     L ::= L, S | S
Assume S is the start symbol.
  1. Find parse trees for the following sentences: 
         i)   (a,a)
     ii)  (a, (a, a))
     iii) (a,((a,a),(a,a)))
  2. Construct a leftmost derivation for each of the sentences in #1.
  3. Construct a rightmost derivation for each of the sentences in #1.
  4. Eliminate the left-recursion from the grammar.
  5. Construct a recursive descent parser for the modified grammar. Show the behavior of the parser on the sentences in #1. 
3.2
Give regular expressions or CFG for the following languages.
  1. Strings of 0's and 1's with an equal number of 0's and 1's.
  2. Strings of 0's and 1's with an unequal number of 0's and 1's.
  3. Context free language over {a,b}: L={anbn}