CSCI 4602
Fall 2000
Practice questions for quiz 2.

  1. Let BAL be the set of all strings of left and right parentheses that are balanced. A string of parentheses that is balanced requires not only a right parenthesis for each left parenthesis, but also correct nesting. Here is a context-free grammar that describes BAL. 
         S  -> S S
     S  -> ( S )
     S  -> epsilon
    (where epsilon is the empty string). Prove that BAL is not regular.

  2. Using the context-free grammar for BAL in the preceding exercise, show a derivation and a parse tree for string (())(()()).

  3. Give a context-free grammar for the language {w#x | w and x are strings over alphabet {a,b}, and wR is a substring of x}. The alphabet of this language is {a,b,#}. Another way to describe the same language is {w#xwRy | w,x,y in {a,b}*}.