CSE 413 Winter 2001

Assignment 5 -- Sample Solution for Written Problems

1. Consider the following grammar:
                   S ::= AB
                   A ::= Aa | bB
                   B ::= a | Sb
1. What are the terminals, nonterminals, and start symbol for this grammar?
   
   terminals = {a,b}
   non-terminals = {S,A,B}
   start symbol = S
   
2. Draw parse trees for the following sentences:
1. baa
   
   
   
2. baabaab
   
   
   
3. Give a leftmost derivation of the sentences in (b).
   
   (i) baa: S => AB => bBB => baB => baa
   (ii) baabaab: S => AB => AaB => bBaB => baaB => baaSb => baaABb =>
   baabBBb => baabaBb => baabaab
   
   
2. Give a context free grammar that generates the language containing all palindromes containing a's and b's.  A palindrome is a string that reads the same from left to right or right to left.  Examples: a, b, bab, abba, babaaabab, ... .
   
   S -> a | b | aa | bb | aSa | bSb