CSCI 4602
Fall 2002
Practice questions for quiz 2

1. Show that the language {aⁿba²ⁿ | n > 0} is not regular. This language contains strings {abaa, aabaaaa, aaabaaaaaa, ...}.

2. If L is a language then L² is the language {xy | x in L and y in L}. Show that the regular languages are closed under squaring. That is, if L is regular then so is L².

3. 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). show a derivation and a parse tree for string (())(()()).

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

5. Does there exist a language that is regular, but that is not context free?